[백준] 1260: DFS와 BFS, python 구현

1. 입력 코드 구현

해당 코드에서 인접 리스트가 정렬되어야 작은 수를 우선으로 탐색한다.

DAT(Direct Access Table)를 위한 visited 변수를 만듦

node, edge, st_node = map(int, input().split())
adj_list = [[] for _ in range(node+1)]
for _ in range(edge):
    i, j = map(int, input().split())
    adj_list[i].append(j)
    adj_list[j].append(i)
adj_list = [sorted(i) for i in adj_list]

visited = [0]*(node+1)

 

2. DFS 구현

dfs는 깊이 우선 탐색이기 때문에 stack으로 구현한다.

노드를 받기위한 stack을 list 형태로 구현하고, append, 방문처리 등을 진행

stack = []
def dfs(current):
    # 해당 문제는 종료조건 없어도 됨 ! -> 완전탐색이기 때문
    # if (종료조건):
    #     return

    for i in adj_list[current]:
        # 방문했다면 pass
        if visited[i]:
            continue;

        stack.append(i)
        visited[i] = 1
        dfs(i)

3. BFS 구현

bfs는 너비 우선 탐색이다. Queue로 구현한다. 이는 물결이 퍼져나가는 듯한 알고리즘으로 flood fill, 짧은 거리 탐색?에 유용할 것으로 보인다.

노드를 받기 위한 q를 변수로 생성하고 collections의 deque를 이용하여 쉽게 구현 가능하다.

from collections import deque

q = []
def bfs(current):
    queue = deque()
    queue.append(current)
    visited[current] = 1

    while queue:
        now = queue.popleft()
        q.append(now)

        for i in adj_list[now]:
            if visited[i]:
                continue

            queue.append(i)
            visited[i] = 1

4. 실행 및 출력

dfs를 실행하기 전, 첫 노드를 방문처리 먼저 함 ! 

출력 시, 리스트로 출력하니 자꾸 틀렸다고 해서 뭐가 잘못 되었는지 한참 찾았다...

리스트가 아니라 문자열?로 출력해야함 ! print의 end 옵션을 사용하여 출력하였음

visited[st_node] = 1
stack.append(st_node)
dfs(st_node)
visited = [0]*(node+1)
bfs(st_node)

for i in stack:
    print(i, end=' ')
print()
for i in q:
    print(i, end=' ')