💻 [백준 - 1260] 파이썬 DFS와 BFS(기본 구현 자세히)

문제:  https://www.acmicpc.net/problem/1260

 

나의 이해를 위한 상세풀이 ! 

다른 분의 블로그를 보며 찬찬히 이해해 나갔다. 

 

1. 행렬 만들기 

N, M, V = map(int, input().split())

# 행렬 만들기 
graph = [[0]*(N+1) for _ in range(N+1)] # 정점의 개수만큼 행렬 생성 
for i in range(M): # 정점간의 연결 표시하기 위해 
    a, b = map(int, input().split()) 
    graph[a][b] = graph[b][a] = 1

 

graph를 N(정점) 개수 만큼 행렬을 생성한다. 

N = 4일 때, [[0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]

graph = 0 0 0 0 0 

              0 0 0 0 0

              0 0 0 0 0

              0 0 0 0 0

              0 0 0 0 0

 

정점의 개수만큼 행렬을 생성했으니까, 이제 정점 간의 연결을 1로 표시해 준다. 

만약 '1 2' 가 입력된다면 정점 1과 정점 2가 연결되어 있다는 뜻이므로 0을 1로 바꿔준다. 

graph[1][2] = graph[2][1] = 1

예제 입력1 처럼 1 2, 1 3, 1 4, 2 4, 3 4를 입력해 주면 그래프는 아래와 같이 된다. 

graph = 0 0 0 0 0

               0 0 1  1  1

               0 1  0 0 1

               0 1  0 0 1

               0 1  1  1 0

 

2. 방문 리스트 만들기 

# 방문 리스트 행렬 
# 노드가 스택과 큐에 들어간 적이 있는지를 확인(한 번 들어갔던 노드는 다시 못 들어감) 
visited1 = [0]*(N+1) 
visited2 = visited1.copy()

 

DFS는 스택을, BFS는 큐를 사용한다. 이 때, 스택과 큐에 한 번 들어갔던 노드는 다시 방문하지 않는다. 

즉, 이 노드가 스택과 큐에 들어갔다면 다시 넣지 않도록 이를 확인하는 리스트가 필요하다. 

 

N = 4 이면 visited1 = [0, 0, 0, 0, 0]이고,

만약 1번 노드에 방문했다면 [0, 1, 0, 0, 0]이 된다. 

 

3. DFS 함수 만들기 

# DFS 함수 만들기 (재귀 이용)
def dfs(V):
    visited1[V] = 1 
    print(V, end=' ') 
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

 

탐색을 시작하는 번호 1부터 탐색을 시작한다. 

먼저 노드 1이 시작이므로 1을 방문 처리한다. 

그러면 visited1[1] = [0, 1, 0, 0, 0]이 될 것이다. 이는 1번 노드가 스택에 들어간 적이 있다는 기록이다. 

 

1번 노드를 방문했으므로 1번 노드를 출력한다. 

print(V, end=' ')

 

이후 for문을 돌려서 if graph[V][i] == 1로

graph[1][1], graph[1][2], graph[1][3], graph[1][4] 를 확인한다.

위에서 행렬로 간선을 1로 표시해뒀으므로 1과 연결된 노드를 찾는다.

 

1과 2,  1과3, 1과 4 모두 연결돼있으므로 graph[1][2] == 1 이 모두 True가 된다. 

여기서 and visited1[i] == 0 으로 2번 노드가 스택에 들어갔던 적이 있는지 확인해야 한다. 

만약 2번 노드가 스택에 들어간 적이 있다면 방문리스트가 1로 되어 False가 된다. 

 

즉, 1과 연결된 노드 중 방문 기록이 없는 노드를 찾는 코드이다. 

if graph[v][i] == 1 and visited1[i] == 0:

 

1과 연결된 노드 중 방문 기록이 없는 노드가 있다면 

dfs(i)로 재귀함수를 돌린다. 

 

dfs(2)는 다시 위의 과정을 돌려서 2를 방문처리하고, 2와 연결된 노드를 찾는다. 

이렇게 계속 연결된 노드들을 찾아 '깊이우선탐색'을 진행한다. 

 

3. BFS 함수 만들기 

# BFS 함수 만들기 
def bfs(V):
    queue = [V]
    visited2[V] = 1 # 방문 처리 
    while queue:
        V = queue.pop(0) # 방문 노드 제거 
        print(V, end = ' ')
        for i in range(1, N+1):
            if(graph[V][i] == 1 and visited2[i]==0):
                queue.append(i)
                visited2[i] = 1 # 방문 처리

 

탐색 시작 노드 V를 큐에 먼저 넣는다. queue = [V] 

이후 방문리스트 visited2[V] = 1로 방문 처리한다. 

V=1 이므로 visited2[1] = [0, 1, 0, 0, 0]이 된다. 

 

이제 while queue:로 큐에 값이 없을 때까지(탐색이 끝날 때까지) 반복한다. 

queue.pop(0)으로 0번째 요소를 돌려주고 삭제한다. 

V=1 일 때, 

queue = [1], visited2[1] = [0, 1, 0, 0, 0]인 상태가 되고 

V = queue.pop(0)을 해주면 queue[], V = 1이 된다. 

1을 꺼냈으니 1을 출력한다. print(V, end = ' ') 

 

이후 for 문으로 연결된 노드들을 탐색한다. 

원리는 dfs와 같다. 

 

bfs 과정을 살펴보자. 

V = 1

queue = [1] 

visited[1] = 1 # [0, 1, 0, 0, 0]

 

while 문 들어가서, 

queue = [], V =1 # 1 출력 

for 문 들어가서, 

노드 1과 2가 연결되고, 2가 방문된 적 없으므로 

graph[1][2] == 1 and visited2[2] ==0 에 해당하므로 

queue = [2] 

visited[2] = 1로 방문 처리 # [0, 1, 1, 0, 0]

 

노드 1과 3이 연결되고, 3이 방문된 적 없으므로

graph[1][3] == 1 and visited2[3] ==0 에 해당하므로 

queue = [2, 3] 

visited[3] = 1로 방문 처리 # [0, 1, 1, 1, 0]

 

노드 1과 4가 연결되고, 4가 방문된 적 없으므로

graph[1][4] == 1 and visited2[4] ==0 에 해당하므로 

queue = [2, 3, 4] 

visited[4] = 1로 방문 처리 # [0, 1, 1, 1, 1]

 

모든 연결 노드 확인 후 for 문 반복 끝 

 

queue에 값이 있으므로 while 문 탈출 안 하고 다시 반복 

V = 2 이므로 2 출력 

queue = [3, 4] 

graph[2][1]==1 and visited[2] ==0 에 해당하지 않으므로 큐에 다시 넣지 않음.

graph[2][2], graph[2][3], graph[2][4] 도 마찬가지임 

아무것도 추가되지 않고 for 문 빠져나감 

 

V= 3 이므로 3 출력 

queue = [4] 

graph[3][1]==1 and visited[2] ==0 에 해당하지 않으므로 큐에 다시 넣지 않음.

graph[3][2], graph[3][3], graph[3][4] 도 마찬가지임 

 

V= 4 이므로 4 출력 

graph[4][1]==1 and visited[2] ==0 에 해당하지 않으므로 큐에 다시 넣지 않음.

graph[4][2], graph[4][3], graph[4][4] 도 마찬가지임 

 

queue = [ ]로 while 종료 

 

💡 최종 코드

N, M, V = map(int, input().split())

# 행렬 만들기 
graph = [[0]*(N+1) for _ in range(N+1)] # 정점의 개수만큼 행렬 생성 
for i in range(M): # 정점간의 연결 표시하기 위해 
    a, b = map(int, input().split()) 
    graph[a][b] = graph[b][a] = 1 

# 방문 리스트 행렬 (방문한 노드를 담음)
# 노드가 스택과 큐에 들어간 적이 있는지를 확인(한 번 들어갔던 노드는 다시 못 들어감) 
visited1 = [0]*(N+1) # ex. [0, 0, 0, 0, 0]
visited2 = visited1.copy()

# DFS 함수 만들기 (재귀 이용)
def dfs(V):
    visited1[V] = 1 # 방문 처리 
    print(V, end=' ') # 첫번째 노드가 방문했으므로 출력 
    for i in range(1, N+1):
        if graph[V][i] == 1 and visited1[i] == 0:
            dfs(i)

# BFS 함수 만들기 
def bfs(V):
    queue = [V]
    visited2[V] = 1 # 방문 처리 
    while queue:
        V = queue.pop(0) # 방문 노드 제거 
        print(V, end = ' ')
        for i in range(1, N+1):
            if(graph[V][i] == 1 and visited2[i]==0):
                queue.append(i)
                visited2[i] = 1 # 방문 처리 

dfs(V)
print()
bfs(V)

 

 

 

참고 사이트:

https://velog.io/@falling_star3/백준Python-1260번-DFS와BFS

[백준][Python] 1260번 DFS와 BFS(DFS/BFS 기본 구현 자세히)