문제 설명

전체 코드

from collections import deque

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

matrix = [[] for _ in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    matrix[a].append(b)
    matrix[b].append(a)

def dfs(v):
    visited[v] = 1
    print(v, end=" ")

    for i in matrix[v]:
        if visited[i] == 0:
            visited[i] = 1
            dfs(i)

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

    while q:
       v = q.popleft()

       print(v, end=" ")

       for i in matrix[v]:
           if visited[i] == 1:
               visited[i] = 0
               q.append(i)

dfs(1)
print()
bfs(1)

해결 방법

dfs와 bfs의 개념을 알 수 있는 문제이다. 간단하게 정리하면

• DFS : 이어달리기, 바통터치 느낌 (한 정점에서 이어진 다른 정점 간 다음, 그 정점과 이어진 정점 순차적으로 이어주기)
• BFS : 와이파이 느낌 (우선 한 정점과 이어진 모든 정점을 들른 후, 다음 정점도 마찬가지로 시작)
• dfs의 경우 : 1에서 시작해서 이어져있는 2로 간후, 2와 이어져있는 4로 가고, 4와 이어져있는 3으로 감 (바통터치)
• bfs의 경우 : 1(공유기)에서 시작해서 이어져있는 2로 간후, 3도 가고난 후, 2(공유기)와 이어진 4로 간 후, 3(공유기)과 이어진 4로 감

코드는 중요한 부분만 집고 넘어가겠다. 문제에서 간선은 양방향이라 하였으므로 입력받은 두 정점 a,b를
matrix[a].append(b), matrix[b].append(a) 이런식으로 표현하였으며 dfs의 1번 정점부터 시작하여 그 matrix[해당 정점]
의 원소에서 visited[원소]가 0이면 1로 바꾸고 재귀적으로 그 원소를 dfs(원소)이렇게 넣고 재귀를 사용한다.

bfs의 경우는 deque을 선언하고 q라는 deque에 정점의 값을 넣으며 dfs와 마찬가지로 중복을 확인해주고 중복되지 않고
그 값이 matrix[정점]의 원소이면 q에 넣고 반복문을 돌리는 형식으로 구해준다.

이 코드는 정말 기본적인 dfs와 bfs의 코딩으로 처음 보는 사람들은 꼭 이해하고 반복하는 것을 추천한다.