[백준] 1260. DFS와 BFS

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

1260번: DFS와 BFS

 

개요

이번 내용은 dfs, bfs이다.

 

풀이 코드

from collections import deque
import queue
import sys

input = sys.stdin.readline

def bfs(v):
    global bfsAnswer
    bVisited[v] = True
    bfsAnswer += f"{v} "
    queue = deque()
    queue.append(v)
    while queue:
        i = queue.popleft()
        for j in graph[i]:
            if not bVisited[j]:
                queue.append(j)
                bVisited[j] = True
                bfsAnswer += f"{j} "

def dfs(v):
    global dfsAnswer
    dVisited[v] = True
    dfsAnswer += f"{v} "
    for i in graph[v]:
        if not dVisited[i]:
            dfs(i)
    
    
n,m,v = map(int, input().split())

graph = [[] for i in range(n+1)]
bVisited = [False]*(n+1)
dVisited = [False]*(n+1)

bfsAnswer = ""
dfsAnswer = ""

for i in range(m):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

for i in graph:
    i.sort()

dfs(v)
bfs(v)
print(dfsAnswer)
print(bfsAnswer)

주의할 점

1. 이중 리스트를 만들 때 [[]]*n 과 같은 방법으로 만들면 [[], [], []] 이렇게 생긴 내부의 리스트들이 하나의 객체를 가르키기 때문에 하나를 바꾸면 나머지도 다 바뀌게된다.

따라서, [[] for i in range(n)] 이렇게 리스트 Comprehension으로 만들어 줘야 한다. 실제로 graph[n1] is graph[n2]로 같은 객체를 의미하는지 테스트를 해보면 전자는 True, 후자는 False가 나와서 각각 다른 객체가 생성되었음을 알 수 있었다.

 

2. 처음에 아무 생각없이 그래프 정보를 추가했었는데 노드와 노드가 "연결된 관계"를 고려해서 양쪽 노드에 해당하는 정보를 넣어줘야 한다.

이때, 이중 리스트를 만드는 게 처음이라 약간 해맸지만 1번의 방식으로 이중리스트를 만들어 해결했다.

 

3. dfs, bfs는 기본적으로 순서가 어떻든 결국 탐색이 되지만 정답 조건에서는 낮은 순서부터 탐색을 해야 하는 조건이 내포되어 있어서 리스트 내부의 요소들을 한 번씩 정렬을 해줘야 했다. 정렬은 for를 돌면서 각 리스트를 sort()하는 방식으로 진행했다.