백준[1260] - DFS와 BFS

 

 

문제

1260번: DFS와 BFS

 

 

 

작성한 코드

from collections import deque
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def bfs(v): 
    q = deque([v])
    visited[v] = True

    while q:
        e = q.popleft()
        print(e, end=" ")
        
        for i in graph[e]:
            if visited[i] == False:
                q.append(i)
                visited[i] = True

N, M, V = map(int, input().split())
graph = [[] for _ in range(N+1)]

for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in graph:
    i.sort()

visited = [False] * (N+1)
dfs(V)
print()

visited = [False] * (N+1)
bfs(V)

- DFS와 BFS를 한 번에 정리할 수 있는 좋은 문제인 것 같다.

- 이전 문제들과 동일하게 코드를 작성했다가 계속해서 오답이라고 해서 의문을 가졌다.

- 문제 분석을 하다가 깨달은 점 : 이전 문제들은 방문 순서를 출력하는 것이었다면, 이번 문제는 방문한 노드 자체를 차례로 출력하는 것

- 이전 문제들과 문제 푸는 방식은 동일하지만, 순서 출력은 필요가 없기 때문에 True/False로 조금 더 간단한 코드로 작성해보았다.

 

[이전 문제 풀이와 다른 점]

- 이전에는 변수 order를 사용해서 방문할 때마다 order의 값을 1씩 증가시킨 후, 해당 순서들이 담긴 visited 리스트의 값을 한 번에 출력했다면 // 이번에는 단순히 방문 여부를 True/False로 나타내어 방문할 때마다 해당 노드 번호를 바로바로 출력하였다.

- 이전에는 visited에 숫자가 들어가기 때문에 visited = [0] * (N+1) 로 해줬다면 // 이번에는 True/False가 들어가기 때문에 visited = [False] * (N+1) 로 해주었다. (방문을 했다면 True, 방문하지 않았다면 False)