[백준 13023][파이썬] DFS 구현 방법

DFS 구현 방식에는 여러 방법들이 존재하는데 DFS 문제를 풀 때마다 헷갈려서 이번에 확실하게 외우기 위해서 포스팅을 작성한다.

 

https://www.acmicpc.net/problem/13023

13023번: ABCDE

전형적인 DFS 문제이다.

 

연결 여부

가장 먼저 노드끼리 연결 여부를 판단해야 한다.

 

이 방법에는 크게 인접 행렬 방식과 연결 리스트 방식이 있다.

 

5개의 노드가 있다면 5x5 행렬을 만들어서 arr[a][b]가 True라면 a와 b가 연결되어 있다는 것을 의미한다.

 

1. 인접 행렬

 

위 문제에서 예제 입력1을 기준으로 행렬을 만들어보면 다음과 같다.

	0	1	2	3	4
0	F	T	F	F	F
1	T	F	T	F	F
2	F	T	F	T	F
3	F	F	T	F	T
4	F	F	F	T	F

이 행렬을 만들 때 주의해야할 점은 a와 b가 연결되어 있다면 arr[a][b]만 True를 저장하는 것이 아니라 arr[b][a]도 True를 저장해야 한다는 점이다.

 

이렇게 인접 행렬로 구현을 하게 되면 연결된 노드의 수가 적을 때 메모리 낭비가 발생한다.

 

만약 노드의 수가 10,000개라면 10,000 x 10,000 행렬을 만들어야 하는데 연결된 수가 5개 정도라면 메모리 낭비가 심하다.

 

파이썬 코드로 구현해보자.

arr=[[False]*n for _ in range(n)] #인접 행렬 생성 
for _ in range(m):
    a, b = map(int, input().split())
    arr[a][b]=True
    arr[b][a]=True

2. 연결 리스트

 

연결 리스트 방식은 인접 행렬의 메모리 낭비를 막기 위한 방법이다.

 

a와 b가 연결되어 있다면 a 리스트에 b를 추가하는 것이다.

 

이 또한 a와 b가 연결되어 있다면 a 리스트에 b를 추가하고 b 리스트에 a를 추가하면 된다.

 

파이썬 코드로 구현해보자.

arr=[[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)

방문 여부

DFS를 구현하기 위해서는 방문 여부를 판단할 수 있어야 한다.

 

a - b - c가 연결되어 있는 경우 a에서 b를 방문했다고 하자.

 

그러면 b로부터 다시 연결된 노드에 방문을 해야 한다.

 

그런데 b에 연결된 노드는 a가 존재하기 때문에 다시 a를 방문하는 것을 막아야 한다.

 

그렇기 때문에 방문 여부를 기록해두고 이미 방문한 노드는 방문하지 말아야 한다.

 

한 노드로부터 연결된 모든 노드에 방문하는 DFS 코드도 인접 행렬 방식이냐 연결 리스트 방식이냐에 따라 달라진다.

 

1. 인접 행렬

def DFS(k, cnt):
    if cnt==5:
        print(1)
        exit()
    for i in range(n): #연결된 거 조사
        if arr[k][i] and not visited[i] : #연결되어 있으며 아직 방문하지 않은 노드
            visited[i]=True
            DFS(i, cnt+1)
            visited[i]=False

인접 행렬 방식은 방문한 노드로부터 모든 노드를 조사한다.

 

연결된 노드이면서 아직 방문하지 않은 노드일 경우 재귀적으로 DFS 함수를 호출하는 것이다.

 

2. 연결 리스트

def DFS(k, cnt):
    if cnt==5:
        print(1)
        exit()
    for i in arr[k]: #연결된 거 조사
        if not visited[i]: #아직 방문안했으면 방문
            visited[i]=True
            DFS(i, cnt+1)
            visited[i]=False

연결 리스트 방식은 조건문이 좀 간단해졌는데 해당 리스트에 존재하는 모든 값은 연결된 노드이기 때문이다.

 

그리고 잘 보면 DFS를 호출하기 전에 해당 노드를 방문했다고 기록해두었다가 호출이 끝나면 다시 방문하지 않았다고 기록을 해 둔 모습을 볼 수 있다.

 

위와 같이 두 경로가 있을 때 A 경로를 갔다가 막혔을 경우 다시 되돌아와야 한다.

 

이 되돌아오는 과정에서 방문했던 노드를 다시 방문하지 않았다고 바꿔줘야 한다.

 

그리고 자세히보면 DFS를 실행할 때마다 cnt 값을 증가시키고 있는데 이는 몇 개가 연결되어 있는지 알아야 할 때 사용한다.

 

이제 이 탐색을 처음 시작할 때의 코드는 다음과 같다.

for i in range(n):
    visited[i]=True
    DFS(i, 1)
    visited[i]=False

처음 탐색을 시작할 때는 방문 여부를 표시하지 않으므로 추가해준 모습이다.

 

<전체 코드>

import sys
input=sys.stdin.readline
def DFS(k, cnt):
    if cnt==5:
        print(1)
        exit()
    for i in arr[k]: #연결된 거 조사
        if not visited[i]: #아직 방문안했으면 방문
            visited[i]=True
            DFS(i, cnt+1)
            visited[i]=False

visited=[False]*2000
n, m = map(int, input().split())
arr=[[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    arr[a].append(b)
    arr[b].append(a)
for i in range(n):
    visited[i]=True
    DFS(i, 1)
    visited[i]=False
print(0)

정리

 

인접 행렬

다음 노드를 방문할 때 연결 여부와 방문 여부를 파악해야 한다.

 

연결 리스트

다음 노드를 방문할 때 방문 여부를 파악해야 한다.

 

공통

1. a와 b가 연결되어있다면 a-b, b-a 모두 연결되었다고 표현을 해줘야 한다.

2. DFS를 실행하기 전에 해당 노드를 방문했다고 하고 실행 후에 해당 노드를 방문하지 않았다고 바꿔야 한다.

3. 연결된 노드의 개수를 구해야 한다면 DFS의 두 번째 인자로 1이 증가한 값을 넘겨줘야 한다.