[파이썬] 백준 5567 : 결혼식

[파이썬] 백준 5567 : 결혼식

5567번: 결혼식 (acmicpc.net)

5567번: 결혼식

실버 2

그래프, BFS, DFS

---

접근

예제 1을 도식화하면 다음과 같다.

 

친구의 친구까지만 초대가 되므로 2, 3, 4번 친구까지가 범위에 해당될 것이다.

기존의 bfs방식은 방문한 정점과 그렇지 않은 정점을 1, 0 (또는 True, False)로 구분하기 때문에 친구의 친구와(4번) 친구의 친구의 친구(5번)를 구별할 수가 없다.

 

따라서 방문한 번호를 다르게 주는 방법으로 이를 구분할 수 있었다.

 

 

코드

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

def bfs(start):
    queue = deque([start])
    visited[start] = 1
    
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if v == 1 and visited[i] == 0 : # 1의 친구들에게 방문점수 3 부여
                visited[i] = 3
                queue.append(i)
                
            elif visited[v] == 3 and visited[i] == 0:  # 방문점수 3의 친구들에게 방문점수 2 부여
                visited[i] = 2
                queue.append(i)
                
            elif visited[i] == 0:  # 그외는 방문점수 1 부여
                visited[i] = 1
                queue.append(i)

n = int(input().rstrip()) # 동기 수, 간선
m = int(input().rstrip())
graph = [[] for i in range(n+1)]
visited = [0] * (n+1)
for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(1)
cnt = 0
for i in range(2, n+1):
    if visited[i] >= 2:
        cnt += 1
print(cnt)

 

다른 사람 코드

1을 기준으로 멀어질수록 방문 리스트의 check의 값을 증가시켜주는 방법으로 구분한다.

from collections import deque

def bfs(node):
    queue = deque()
    queue.append(node)
    while queue:
        node = queue.popleft()
        for n in graph[node]:
            if check[n] == 0:
                check[n] = check[node]+1
                queue.append(n)
    
n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)
check = [0]*(n+1)
check[1] = 1
bfs(1)
res = sum([1 for t in check if 2 <= t <= 3])
print(res)