[백준 파이썬] # 1260 DFS와 BFS

Silver II

# 1260 DFS와 BFS

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

1260번: DFS와 BFS

 

풀이

from collections import deque

n, m, v = map(int, input().split())

graph = [[] for _ in range(n+1)]

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

    # Q. for 구문 안에서 행해져야 정답처리?
    graph[s].sort()
    graph[e].sort()

visited = [False] * (n+1)

def dfs(graph, v, visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
    visited = [False]*(n+1)    # visited가 dfs에 의해 변경 되었으므로 다시 정의 필요
    queue = deque([v])
    visited[v] = True
    while queue:
        pop = queue.popleft()
        print(pop, end = ' ')
        for i in graph[pop]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

dfs(graph, v, visited)
print()    # dfs와 bfs를 동시에 출력하기 위함
bfs(graph, v, visited)

 

• DFS, BFS 자료 구조에 관한 가장 기본적인 문제
• graph 정의부터 사용자 함수 정의, deque 구조 파악 등에서 어려움이 많았다
• visited 공간을 n+1개로 정의해주는 이유는 supernode 인 graph[0]을 사용하지 않기 때문이라 이해하자
• Q.sort가 for 문 안에서 행해져야 하는 이유가 있나?
• Q.print()에 옵션 없이 사용하기도 하나?