[Python/파이썬] 백준 1260 : DFS와 BFS

DFS와 BFS를 공부 중인데,

이론적으로 이해하는 건 되지만 계속 헷갈려서 코드만 정리하면서 써보려구요.

 

갑니다.. 더 친절한 설명을 원하면 다른 블로그를 참고해주세요!

 

from collections import deque
from sys import stdin
input = stdin.readline

# 입력을 받는 곳입니다.
n,m,v = map(int, input().split())

# 1. 그래프 초기화
## 인덱스를 1부터 시작하기 위해서 n+1 을 해줍니다.
## 일반적으로 그래프의 노드 번호는 1부터 시작하는 경우가 많습니다.
## n은 실제 노드의 개수이고, 노드의 번호는 1부터 n까지이니 리스트의 크기를 n+1로 설정하여
## 인덱스 1부터 n까지 사용할 수 있도록 초기화를 한 것입니다.
### 이렇게 하면 노드와 인덱스를 일치시킬 수 있습니다.
### 더 많은 설명은 아래에 첨부하겠습니다.
graph = [[0]*(n+1) for _ in range(n+1)]

# 2. 방문 여부 초기화
dfs_visited = [False] * (n+1)
bfs_visited = [False] * (n+1)

# 3. 그래프 정보 입력
for _ in range(m):
    x, y = map(int, input().split())
    graph[x][y] = 1
    graph[y][x] = 1

# 깊이 우선 탐색 함수
def dfs(v):
    dfs_visited[v] = True	# 현재 노드를 방문 처리
    print(v, end=' ')		# 현재 노드 출력
    for i in range(1,n+1):
    	# 방문하지 않았고, 연결된 노드라면 재귀로 호출합니다.
        ## not visited : 방문하지 않은 노드라면?
        ## graph[v][i] == 1 : 연결이 되어있다면?
        ### 연결된 부분은 위에서 graph[][] = 1 로 할당해주었잖아요!
        if not dfs_visited[i] and graph[v][i] == 1:
            dfs(i)

# 너비 우선 탐색 함수
def bfs(v):
    bfs_visited[v] = True	# 현재 노드를 방문 처리
    queue = deque()
    queue.append(v)			# 큐에 현재 노드를 추가합니다. QUEUE, NOT STACK!!
    while queue:
        popv = queue.popleft()	# 큐에서 노드를 하나 꺼내와 popv에 할당. (처음 들어간 게 나오겠죠)
        print(popv, end=' ')	# 꺼내온 노드 출력
        for i in range(1,n+1):
        	# 방문하지 않았고, 연결된 노드라면 큐에 추가하고 방문 처리를 합니다.
            ## 조건은 위에 dfs와 같습니다.
            ## 하지만, append를 통해 큐에 추가해주죠 (추가된 노드에 연결된 노드를 나중에 확인해야 하니까요)
            if not bfs_visited[i] and graph[popv][i] == 1:
                queue.append(i)
                bfs_visited[i] = True

dfs(v)
print()
bfs(v)

 

코드를 보고 헷갈렸던 부분은 1번으로 적어놓은 graph와 visited를 설정할 때 입니다.

저렇게 코드를 써두면,

node의 개수 즉, n이 3일 때!      graph와 visited는 각각

 

graph = [0, [0,0,0], [0,0,0], [0,0,0]]

visited = [False, False, False, False]

 

가 되는 것입니다. 이렇게 설정하면 각 리스트의 맨 앞은 사용하지 않고

1번 노드와 2번 노드가 연결되어 있다면

graph[1][2] = 1,   graph[2][1] = 1   처럼 간편하게 알아볼 수 있고,

visited 도 그냥 1번 노드 방문했었나? 하면

visited[1]을 확인하면 끝나는 것이죠.

 

이 부분을 직접 돌려보며 계속 이해하려고 노력했고, 후에 공부할 때 도움이 잘 되었던 것 같습니다. (이해하는데..)

 

끝!