DFS(깊이 우선 탐색)

주어진 그래프나 트리의 모든 정점을 순회 하고자 할 때 사용 할 수 있는 알고리즘에는 DFS, BFS가 있다. 그 중 먼저 깊이 우선 탐색을 알아보자.

 

깊이 우선 탐색 이름에 걸맞게 DFS는 아래로 아래로 내려가다가 끝을 찍으면 다시 돌아가서 다른 우물을 다시 아래로 아래로 파는 성격의 알고리즘이다.

위 트리를 DFS로 탐색해보자.

 

먼저 1번 정점에서 탐색을 시작한다고 하자.

 

1번 정점에서 아직 방문하지 않은 인접한 정점 중 하나를 선택해 방문한다.

 

여기서 중요한점은 한 정점으로 부터 아래로 아래로 순회해야하기 때문에, 만약 1번 정점에서 2번 정점을 방문한다 했을 때, 1번 정점의 인접한 정점들을 우선적으로 순회하는것이 아니라 2번정점의 인점한 정점들을 우선적으로 순회한다!

 

그렇다면 1번에서 출발해 2번 정점을 방문했다 했을 때, 아직 방문하지 않은 정점들 중, 1번 정점에 인접한 7, 8을 순회하는것이 아니라 2번 정점에 인접한 3번과 6번을 우선적으로 탐색해야 하는것이다.

 

이후 3번 정점을 방문하고 4번, 끝을 찍었으니 3번으로 돌아가 5번, … 이렇게 12번 정점을 방문하고 나면 아무리 돌아가도 더 이상 방문할 정점이 없기 때문에 탐색이 종료되고 1번 정점을 시작으로 모든 정점을 순회한 결과가 된다.

 

이렇게 DFS로 위 트리를 순회하면 순회 결과는 다음과 같다.

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12

 

DFS에서 중요한 것은 아래로 내려가서 바닥을 찍으면 어떻게 다시 돌아올까? 라는것이다.

 

‘다시 돌아 나온다’ 스택과 유사하지 않은가?

 

DFS는 해당 정점에서 인접한 정점들을 스택에 넣는다. 그리고 방문하면 POP해서 다음 인접한 정점들을 다시 스택에 넣는다!

 

재귀함수 또한 스택 메모리에 호출들을 쌓아두는 구조니 스택 대신 재귀를 써서도 DFS를 구현 할 수 있다!

---

이제 DFS 알고리즘을 사용한 문제들을 몇가지 풀어보자.

 

보통 DFS로 풀 수 있는 문제들은 BFS를 통해서도 풀 수 있음을 기억하자!

트리의 부모 찾기

11725번: 트리의 부모 찾기

11725번: 트리의 부모 찾기

트리의 부모 찾기는 각 정점의 부모를 찾는 문제이다.

 

위에서 설명했드시 그래프나 트리를 순회 할 땐, 부모 정점에 인접한 자식 정점들을 탐색하는데, 때문에 부모 정점에 인접한 정점들을 스택에 넣을 때 부모를 알 수 있다.

 

그래서 어느 정점을 기준으로 자식 정점을 탐색 할 때 부모 정점을 알 수있다.

 

부모노드를 저장할 리스트를 만들고 인접 정점을 탐색 할 때 그 부모 정점을 리스트에 넣으면 된다.

def dfs(v):
    visited[v] = True

    for node in graph[v]:
        if not visited[node]:
            roots[node] = v
            dfs(node)

전체코드

# 트리의 부모찾기
import sys
sys.setrecursionlimit(10**6)
v = int(sys.stdin.readline())
graph= [[] for _ in range(v+1)]
visited = [False] * (v+1)

roots = [0] * (v+1)

for i in range(v-1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def dfs(v):
    visited[v] = True

    for node in graph[v]:
        if not visited[node]:
            roots[node] = v
            dfs(node)

dfs(1)
for i in range(2, v+1):
    print(roots[i])

• 참고로 그래프를 입력 받을 때 인접 행렬과 인접 리스트로 받을 수 있다. 이번에는 인접 리스트로 받았다.

---

빙산

2573번: 빙산

2573번: 빙산

 

빙산 문제는 특정 좌표(빙산)에 인접한 노드들 중 바다가 있다면 특정 좌표의 값을 인접한 바다 수 만큼 감소시키고, 그래프의 컴포넌트 갯수를 구하는 것 처럼 for 루프를 돌면서 깊이 우선 탐색을 해서 만약 두 컴포넌트 즉 빙산이 두 조각 이상으로 나눠질 때까지 얼마나 걸릴까를 묻는 문제이다.

 

빙산을 녹일 때 한 가지 중요한것이 있다.

 

for 루프는 순차적으로 돌면서 처리하기 때문에, 정점마다 방문해서 0인 지점을 그 순간 처리한다면 1년후 물이된 지점으로 인해서 다음 정점은 1년이 지났음에도 2년이 지난것처럼 될 것이다.

 

따라서 빙산 근처에 있는 얼음 수를 카운팅한 행렬을 만들고 실제 행렬에서 각 행렬에 해당하는 값을 빼 줘야 한다.

 

빙산 녹이는 방법

0	0
1	3

정상적으로 1년이 지나면 아래처럼 되지만

 

정상

0	0
0	2

순차적으로 돌면서 빙산을 녹인다면 0으로 변한 지점 때문에 다음 빙산이 한번 더 녹게 된다. 이점을 조심해서 얼음을 녹여야한다.

 

비 정상

0	0
0	1

# 빙산
import sys

n, m = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

def melting():

    # 정점마다 방문해서 0인 지점을 그 순간 받아서 처리한다면 1년후 물이된 지점으로 인해
    # 다음 정점은 1년이 지났음에도 2년이 지난것처럼 될 것이다.
    # 따라서 빙산 근처에 있는 얼음 수를 카운팅한 행렬을 만들고
    # 실제 행렬에서 각 행렬에 해당하는 값을 빼준다.
    glacier = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0:
                cnt = 0
                for dir in range(4):
                    nx = dx[dir] + i
                    ny = dy[dir] + j
                    if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 0:
                            cnt += 1
                glacier[i][j] = cnt          
    for i in range(n):
        for j in range(m):
            graph[i][j] -= glacier[i][j]
            if graph[i][j] < 0:
                graph[i][j] = 0

def dfs(x, y):
    stack = []
    stack.append((x, y))
    visited[x][y] = True
    
    while stack:
        cx, cy = stack.pop()

        for dir in range(4):
            nx = dx[dir] + cx
            ny = dy[dir] + cy

            if 0 <= nx < n and 0 <= ny < m and graph[nx][ny] and not visited[nx][ny]:
                stack.append((nx, ny))
                visited[nx][ny] = True
res = 0

while True:
    visited = [[False for _ in range(m)]  for _ in range(n)] 
    melting()
    cnt = 0
    res += 1
    flag = False

    for i in range(n):
        for j in range(m):
            if graph[i][j] > 0 and not visited[i][j]:
                # 빙산을 방문처리 해줌
                # 만약 한 덩이라면 해당 좌표는 방문 처리 됐으므로 for 루프를 돌지 않는다.
                dfs(i, j)
                cnt += 1
                flag = True
    if cnt > 1:
        print(res)
        break        
    if not flag:
        print(0)
        break