[Python] 백준 1260번: DFS와 BFS


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

주의 할 점

연결된 노드를 방문할 때 작은 노드부터 방문 한다는 점.
만약 채점 중 11%에서 자꾸 틀린다면 정렬을 확인해봅시다! (3번 틀림 ㅠ)

도움이 된 반례

6 8 1
1 6 
6 2 
2 4 
4 3 
3 5 
5 1 
5 6 
2 3
----
1 5 3 2 4 6 
1 5 6 3 2 4 

반례를 모아 놓은 글: https://www.acmicpc.net/board/view/24356

코드

import sys
from collections import deque
input = sys.stdin.readline
n, m, v = map(int, input().split())

maps = [[] for _ in range(n+1)]
info  = [list(map(int,input().split())) for _ in range(m)]
for a,b in info:
    maps[a].append(b)
    maps[b].append(a)

visited = [False] * (n+1)
dfs = []

def DFS_Recursive(maps, now):
    visited[now] = True
    dfs.append(now)
    for w in sorted(maps[now]):
        if not visited[w]:
            DFS_Recursive(maps, w)
DFS_Recursive(maps, v)
print(*dfs)

bfs = [v]
q = deque()
q.append(v)

while q:
    now = q.popleft()
    visited[now]=True
    for w in sorted(maps[now]):
        if w not in bfs:
            q.append(w)
            bfs.append(w)
print(*bfs)

좋은 웹페이지 즐겨찾기