[Python] 백준 1260번 - DFS와 BFS

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

1260번: DFS와 BFS

 

항상 dxdy 기법에 익숙한 bfs를 dxdy 없이 그냥 큐로 구현하는 것 빼고는 어렵지 않은 문제였다.

 

방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문해야 해서 인접리스트를 sort 해주어야 했는데,

왠지 당연히 입력할 때부터 제대로 정렬해서 줄 것 같다는 근거 없는 생각에 sort를 안 해서 틀렸다.

입력받으면서 각각의 인접리스트 인덱스를 정렬하여 해결하였다.

 

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

def dfs(x):
    print(x, end=' ')
    visited[x] = 1
    for w in adj[x]:
        if not visited[w]:
            visited[w] = 1
            dfs(w)

def bfs(x):
    q = deque()
    q.append(x)
    visited[x] = 1
    print(x, end=' ')
    while q:
        x = q.popleft()
        for i in adj[x]:
            if not visited[i]:
                visited[i] = 1
                q.append(i)
                print(i, end=' ')

n, m, v = map(int, input().split())
adj = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]
for _ in range(m):
    n1, n2 = map(int, input().split())
    adj[n1].append(n2)
    adj[n2].append(n1)
    adj[n1].sort()
    adj[n2].sort()

dfs(v)
print("")
visited = [0 for _ in range(n+1)]
bfs(v)