[파이썬] 백준 5567 : 결혼식 (실버2)

[파이썬] 백준 5567 : 결혼식 (실버2)

 

5567번: 결혼식

---

문제

---

풀이

0. 방향성 생각

기준 노드인 1번 노드로부터 거리가 2 이하인 노드의 개수가 정답이다.

visit을 통해 몇 번째로 방문했는지 업데이트 해주고 정답을 얻는다.

1. 입력

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
visit = [-1]*(n+1)
for _ in range(int(input())):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

무방향 그래프이므로 양쪽 둘다 그래프에 추가해준다.

또한 1번 노드부터 시작이므로 더미 노드인 0번을 만들기 위해 n+1 길이를 가지게 한다.

2. 출력

q = deque()
q.append(1)
visit[1] = 0
while q:
    x = q.popleft()
    for nx in graph[x]:
        if visit[nx] == -1:
            visit[nx] = visit[x]+1
            q.append(nx)

answer = [i for i in visit if i>0 and i<3]
print(len(answer))

큐에 1번 노드를 넣고 탐색을 시작한다.

연결된 노드가 방문처리가 되어있지 않으면 거리 +1을 해주고 큐에 넣는다.

visit 중 거리가 1 2인 노드만 얻는다.

---

전체코드

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]
visit = [-1]*(n+1)
for _ in range(int(input())):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

q = deque()
q.append(1)
visit[1] = 0
while q:
    x = q.popleft()
    for nx in graph[x]:
        if visit[nx] == -1:
            visit[nx] = visit[x]+1
            q.append(nx)

answer = [i for i in visit if i>0 and i<3]
print(len(answer))