[Baekjoon] Graph - 5567 결혼식

문제

https://www.acmicpc.net/problem/5567

 

풀이

그래프 탐색 이용

1. BFS 활용

2. 방문하지 않았으면 방문 (기존 방문 + 1)

3. 인접 정점 할당

 

예시

6
5
1 2
1 3
3 4
2 3
4 5

 

 

코드

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
edges = [[] for _ in range(n + 1)]
visited = [0] * (n + 1)

for _ in range(m):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    edges[x].append(y)
    edges[y].append(x) # 반례


queue = deque([1])
visited[1] = 1

while queue:
    x = queue.popleft()

    for v in edges[x]:
        if not visited[v]:
            queue.append(v)
            visited[v] = visited[x] + 1


print(visited.count(2) + visited.count(3))

 

궁금증

edges[y].append(x)를 넣어야할까요?

→ 네 넣어야합니다.

 

반례

6
4
1 3
1 6
2 6
3 5

2, 6만 넣게 되면 6, 2의 정보를 알 수 없으므로 edges[y].append(x)를 포함하지 않으면 2가 포함되지 않습니다.