문제 설명

전체 코드

from collections import deque

n = int(input())
m = int(input())

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

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

def bfs(v):
    global result

    q = deque([v])
    visited[v] = 1

    while q:
       v = q.popleft()

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

해결 방법

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

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

이 전에 풀었던 "dfs와 bfs" 이 문제와 똑같다. 솔직히 다른 부분이 하나도 없다. 그래도 조금 달라진 점을 서술하자면 정점 1부터 시작하여 bfs라는 함수에 들어왔을때 for문에서 만약 matrix[정점]의 값이 중복이 되지 않았다면 result에 +1을 해주면 끝나는 문제이다.