[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)
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)
Author And Source
이 문제에 관하여([Python] 백준 1260번: DFS와 BFS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@joniekwon/Python-백준-1260번-DFS와-BFS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)