2주차 스터디(23.11.16) - DFS, BFS

2주차 스터디 내용은 DFS, BFS를 집중적으로 학습했습니다.

 

LG전자 코딩테스트도 겹쳐있었던지라 집중적으로 이문제 저문제 풀어봤던 것 같습니다.

 

내용 및 설명 추가 예정

 

 

1. 백준 - 영역 구하기

from collections import deque
M,N,K = map(int,input().split())
A = [[0 for _ in range (0,N)] for _ in range (0,M)]
visited = [[False for _ in range (0,N)] for _ in range (0,M)]
for i in range (0,K): #벽(색칠된 부분) 체크하기
    a =  list(map(int,input().split()))
    for j in range (a[1],a[3]):
        for k in range (a[0],a[2]):
            A[j][k] = 1      
            
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = []
for i in range (0,M):
    for j in range (0,N):
        if A[i][j] == 0 and visited[i][j] == False:
            cnt = 1
            deq = deque()
            deq.appendleft((i,j))
            while deq:
                x,y = deq.popleft()
                visited[x][y] = True
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N:
                        if A[a][b] == 1:
                            continue
                        if visited[a][b] == False and A[a][b] == 0:
                            deq.appendleft((a,b))
                            visited[a][b] = True
                            cnt += 1
            ans.append(cnt)
ans.sort()
print(len(ans))
print(" ".join(str(s) for s in ans))

 

 

어떤 점의 좌표가 주어져있을 때,  그 점의 상하좌우를 전부 훑어보면서 방문한 곳인지 방문하지 않은 곳인지 체크하면서

 

deque에 추가해주면 됩니다. 방법은 dfs던 bfs던 상관 없을 것 같습니다.

 

처음으로 방문한 곳은 방문처리를 해서 이후에 올 수 없도록 하는 조치가 필요하겠습니다.

 

몇개가 붙어있는지 세면 되기 때문에, cnt를 통해 인접한 영역의 갯수를 구하면서 리스트 (ans)에 추가하면 되겠습니다.

 

ans를 오름차순으로 정렬해준 뒤, 출력해주면 되겠습니다.

 

 

 

2. 프로그래머스 - 미로 탐색

from collections import deque
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    deq = deque()
    deq.append((0, 0))
    n = len(maps) #세로 길이 first component
    m = len(maps[0]) #가로 길이 second component
    check = [[False for _ in range (0,m)] for _ in range (0,n)]
    while deq:
        x,y = deq.popleft()
        check[x][y] = True
        for i in range(0,4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < n and 0 <= b < m:
                if maps[a][b] == 0:
                    continue
                else:
                    if check[a][b] == False:
                        maps[a][b] += maps[x][y]
                        check[a][b] = True
                        deq.append((a,b))
                    else:
                        maps[a][b] = min(maps[a][b], maps[x][y] + 1)
                    
            else:
                continue
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]
N,M = map(int,input().split())
A = []
for i in range (0,N):
    a = input()
    b = []
    for j in range (0,len(a)):
        b.append(int(a[j]))  
    A.append(b)
print(solution(A))

 

동일하게 상하좌우로 막히지 않은 곳을 찾아가면서 도착점까지 가면 되겠습니다.

 

주의해야할 점은, 이미 방문한 포인트에 있어서는 어떻게 해야하는가? 가 되겠습니다.

 

그때는 기존값과 새롭게 취한 루트에 대해서의 값을 비교해주면 되겠습니다.

 

그리고 deque가 비워졌음에도 불구하고 도달하지 못한 경우에는 출구에 도달하지 못했다는 뜻이 되겠습니다.

 

3. 프로그래머스 - 무인도 여행

from collections import deque
def solution(maps):
    answer = []
    N = len(maps)
    
    A = [[0 for _ in range (0,len(maps[0]))] for _ in range (0,N)]
    for i in range (0,N):
        for j in range (0,len(maps[0])):
            if maps[i][j] == "X":
                A[i][j] = "X"
            else:
                A[i][j] = int(maps[i][j])
    M = len(maps[0])
    visited = [[False for _ in range (0,M)] for _ in range (0,N)]
    #first ex: n = 4, m = 5
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    for i in range (0,N):
        for j in range (0,M):
            if A[i][j] == "X" or visited[i][j] == True:
                continue
            else:
                cnt = A[i][j]
                deq = deque()
                deq.appendleft((i,j))
                while deq:
                    x,y = deq.popleft()
                    visited[x][y] = True
                    for k in range (0,4):
                        a = x + dx[k]
                        b = y + dy[k]
                        if 0 <= a < N and 0 <= b < M:
                            if visited[a][b] == False and A[a][b] != "X":
                                deq.appendleft((a,b))
                                visited[a][b] = True
                                cnt += A[a][b]
                answer.append(cnt)
    answer.sort()
    if answer == []:
        return [-1]
    else:
        return answer

 

1번과 동일한 유형입니다.

 

단순히 이 경우에는 각 좌표 (i,j)에 방문할때마다 cnt에 A_ij에 해당하는 값을 더해주면 됩니다.

 

이후, cnt 값을 리스트에 추가하면서 오름차순으로 정렬하면 정답이 나옵니다.

 

4. 프로그래머스 - 네트워크

from collections import deque
def solution(n, computers):
    answer = 0
    connection = []
    for i in range (0,n):
        a = []
        deq = deque()
        deq.append((i,i))
        checked = [[False for _ in range (0,n)] for _ in range (0,n)]
        checked[i][i] = True
        a.append(i)
        while deq:
            x,y = deq.popleft()
            a.append(y)
            for z in range (0,n) :
                if computers[y][z] == 1 and checked[y][z] == False:
                    deq.append((y,z))
                    checked[y][z] = True
                    a.append(z)
                else:
                    continue
        a = list(set(a))
        connection.append(a)
    ans = []
    for i in range (0,len(connection)):
        if connection[i] in ans:
            continue
        else:
            ans.append(connection[i])
    answer = len(ans)
    return answer

 

이 경우에는 Directed graph가 아닌 Undirected Graph입니다.

 

예를 들어, i와 j가 연결되어있다 한다면 행렬을 만들 때 A_ij = A_ji = 1로서 설정하는 방식으로 행렬 A를 구성해줍니다.

 

이런 행렬 A를 Adjacency Matrix (인접행렬) 이라고 부릅니다.

 

결국 각 노드에 방문했을 때 이어져있는 모든 노드를 찾아보는 방식이 되겠습니다.

 

그렇게 노드의 끝이 어디인지 찾아가는 방식이 되겠네요.

 

(이 과정에서 연산이 조금 많아질 수 있는데, 이런 경우에는 처음에 A를 받아올 때,

A = [[] for _ in range (0,N)] 이렇게 빈 매트릭스를 만들어준 뒤에, A[i]에 대해서만 사이클을 돌려주면 될 것 같습니다.)

 

 

5. 백준 - 케빈 베이컨의 6단계 법칙

import sys
import math
input = sys.stdin.readline
N,M = map(int,input().split())
A = [[math.inf for _ in range (0,N)] for _ in range (0,N)]
for i in range (0,M):
    a,b = map(int,input().split())
    A[a-1][b-1],A[b-1][a-1] = 1,1
for k in range (0,N):
    for i in range (0,N):
        for j in range (0,N):
            A[i][j] = min(A[i][j], A[i][k] + A[k][j])
answer = []
for i in range (0,N):
    a = sum(A[i]) - A[i][i]
    answer.append(a)
min_val = min(answer)
for i in range (0,N):
    if answer[i] == min_val:
        print(i+1)
        break

 

위에서 언급한 Adjacency Matrix의 예 입니다.

 

친구라는 것이 단방향이 아니라 양방향으로 알고 있는 것을 전제로 하고 있기 때문에, 이렇게 생각해볼 수 있겠습니다.

 

한편, 행렬 2개를 곱해주면서 그 값이 어떻게 되는지 체크하는 것이겠습니다.

 

아이디어로서는 i와 j가 알고있고, j가 k가 알고 있다고 하는 상황에서, i와 k의 관계가 어떨까요?

 

(설명 조금 더 작성)

 

 

 

6. 백준 - 내리막 길 (골드 3)

def f(x,y):
    if x ==  M-1 and y == N-1:
        return 1
    if dp[x][y] != -1:
        return dp[x][y]
    route = 0
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    for i in range (0,4):
        a = x + dx[i]
        b = y + dy[i]
        if 0 <= a < M and 0 <= b < N and graph[x][y] > graph[a][b]:
            route += f(a,b)
    dp[x][y] = route
    return route
M,N = map(int,input().split())
graph = []
dp = [[-1 for _ in range (0,N)] for _ in range (0,M)]
for i in range (0,M):
    a = list(map(int,input().split()))
    graph.append(a)
print(f(0,0))

 

 

 

7. Leet code - Rotting Oranges (medium)

class Solution:
    import copy
    from collections import deque
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])
        checked = [[False for _ in range (0,n)] for _ in range (0,m)]
        deq = deque()
        a = []
        fresh = 0
        for i in range (0,m):
            for j in range (0,n):
                if grid[i][j] == 1:
                    fresh += 1
                if grid[i][j] == 2:
                    a.append([i,j])
        deq.append(a)
        dx = [0,0,1,-1]
        dy = [1,-1,0,0]
        day = 0
        #이미 다 상해있는 경우
        if fresh == 0:
            return day
        #그렇지 않은 경우
        while deq:
            k = fresh
            x = deq.popleft()
            rotten_orange = []
            for i in range (0,len(x)):
                for j in range (0,4):
                    a = x[i][0] + dx[j]
                    b = x[i][1] + dy[j]
                    if 0 <= a < m and 0 <= b < n and grid[a][b] == 1 :
                        grid[a][b] = 2
                        fresh -= 1
                        rotten_orange.append([a,b])
            if k == 0:
                break
            if k == fresh:
                return -1
            else:
                day += 1
                deq.appendleft(rotten_orange)
        return day

 

상한 오렌지는 상하좌우에 있는 오렌지를 전부 상하게 한다는 점에 착목하면 좋을 것 같습니다.

 

 

 

 

8. 프로그래머스 - 게임 맵 최단거리

from collections import deque
def solution(maps):
    answer = 0
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    deq = deque()
    deq.append((0, 0))
    n = len(maps) #세로 길이 first component
    m = len(maps[0]) #가로 길이 second component
    check = [[False for _ in range (0,m)] for _ in range (0,n)]
    while deq:
        x,y = deq.popleft()
        check[x][y] = True
        for i in range(0,4):
            a = x + dx[i]
            b = y + dy[i]
            if 0 <= a < n and 0 <= b < m:
                if maps[a][b] == 0:
                    continue
                else:
                    if check[a][b] == False:
                        maps[a][b] += maps[x][y]
                        check[a][b] = True
                        deq.append((a,b))
                    else:
                        maps[a][b] = min(maps[a][b], maps[x][y] + 1)
                    
            else:
                continue
    if maps[-1][-1] == 1:
        return -1
    else:
        return maps[-1][-1]

 

9. Leet code - Course Schedule (medium)

class Solution:
    from collections import deque
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        v = numCourses
        e = len(prerequisites)
        graph = [[] for _ in range (0,v)]
        indegree = [0 for _ in range (0,v)]
        for edge in prerequisites:
            a,b = edge[0],edge[1]
            graph[a].append(b)
            indegree[b] += 1
        deq = deque()
        for i in range (0,v):
            if indegree[i] == 0:
                deq.appendleft(i)
        result = []
        print(deq)
        if len(deq) == 0:
            return False
        A = []
        while deq:
            now = deq.popleft()
            result.append(now)
            for i in graph[now]:
                indegree[i] -= 1
                if indegree[i] == 0:
                    deq.appendleft(i)
        if len(result) != v:
            return False
        return True

 

위상정렬 (Topological sort)에 대한 개념을 알 수 있었습니다.

일반적인 DFS, BFS와 비슷한 느낌이지만 directed graph를 설정한 후, Route의 끝까지 뚫는 역할을 합니다.

 

 

 

10. 백준 - 전쟁전투 (실버 1)

from collections import deque

N,M = map(int,input().split())
check = [[False for _ in range (0,N)] for _ in range (0,M)]
war = []
for i in range (0,M):
    a = input()
    war_list = []
    for j in range (0,len(a)):
        war_list.append(a[j])
    war.append(war_list)
power1 = 0
power2 = 0
dx = [0,0,1,-1]
dy = [1,-1,0,0]
for i in range (0,M):
    for j in range (0,N):
        if war[i][j] == "W" and check[i][j] == False:
            check[i][j] = True
            deq = deque()
            deq.append((i,j))
            cnt = 0
            while deq:
                x,y = deq.popleft()
                cnt += 1
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N and check[a][b] == False and war[a][b] == "W":
                        deq.append((a,b))
                        check[a][b] = True
            power1 += cnt ** 2
        if war[i][j] == "B" and check[i][j] == False:
            check[i][j] = True
            deq = deque()
            deq.append((i,j))
            cnt = 0
            while deq:
                x,y = deq.popleft()
                cnt += 1
                for k in range (0,4):
                    a = x + dx[k]
                    b = y + dy[k]
                    if 0 <= a < M and 0 <= b < N and check[a][b] == False and war[a][b] == "B":
                        deq.append((a,b))
                        check[a][b] = True
            power2 += cnt ** 2
print(power1,power2)

 

 

 

 

11. 백준 - 숨바꼭질 2 (골드 5)

from collections import deque
N,K = map(int,input().split())
if N >= K:
    print(N-K)
    print(1)
else:
    cnt = 0
    num = [0 for _ in range (0,100001)]
    deq = deque()
    deq.appendleft([N])
    while deq:
        X = deq.popleft() #리스트로 받아옴
        B = []
        for i in range (0,len(X)):
            for y in (X[i] - 1, X[i] + 1, 2 * X[i]):
                if y > 100000 or y < 0:
                    pass
                else:
                    if num[y] == 0 or num[y] == num[X[i]] + 1:
                        B.append(y)
                        if y == K:
                            cnt += 1
                        num[y] = num[X[i]] + 1
                    else:
                        if y == K:
                            cnt += 1
        deq.appendleft(B)
        if cnt != 0:
            break
        else:
            continue
    print(num[K])
    print(cnt)

 

 

 

 

 

 

 

 

12. 프로그래머스 - 타겟 넘버

from collections import deque
def solution(numbers, target):
    answer = 0
    deq = deque()
    deq.append([numbers[0],-numbers[0]])
    cnt = 1
    while cnt < len(numbers):
        A = deq.popleft()
        B = []
        for i in range (0,len(A)):
            B.append(A[i]-numbers[cnt])
            B.append(A[i]+numbers[cnt])
        deq.append(B)
        cnt += 1
    for i in range (0,len(deq[0])):
        if deq[0][i] == target:
            answer += 1
    return answer