[Algorithm] 5567. 결혼식

5567: 결혼식(그래프)

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

• 문제 티어 : S2
• 풀이 여부 : Solved
• 소요 시간 : 27:35

정답 코드

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

N = int(input()) # 2 ~ 500
M = int(input()) # 1 ~ 10000
adj = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().rstrip().split())
  adj[a][b] = adj[b][a] = 1
visited = [False for _ in range(N+1)] # 1번: 상근, 2~N: 친구들
ans = 0

def bfs(cur_v):
  global ans
  dq = deque([(cur_v, 0)]) # 노드, depth(직속친구 : 1, 친구의 친구 : 2)

  while dq:
    cur_v, depth = dq.popleft()
    for i in range(1, N+1):
      if adj[cur_v][i] == 1 and not visited[i] and depth < 2:
        dq.append((i, depth + 1))
        visited[i] = True
        adj[cur_v][i] = 0
        ans += 1

bfs(1)
print(ans-1 if ans else 0) # 상근 본인 빼고

접근 방식

BFS로 풀이한 문제다.

1. M개의 줄에 걸쳐 입력받은 그래프 정보를 인접행렬로 만듦

2. deque에 인자로 들어온 현재 노드를 넣어줄 때,

   • 직속 친구 : depth == 1
   • 친구의 친구 : depth == 2

   위의 조건을 고려해주기 위해 (노드, depth=0)의 튜플 형태로 넣어줌

3. dq의 cur_v 노드 순회 조건

   1. 현재 노드의 이웃한 노드인지 (adj[cur_v][i] == 1)

   2. 방문한 적 없는 노드인지 (not visited[i])

   3. 현재 노드와의 depth가 2 미만인지

      → 2 이상이면 친구의 친구 관계를 넘어 상근이와 모르는 관계가 됨

   위 3조건 만족 시,

   1. dq에 넣고
   2. 방문처리하고
   3. 인접행렬 값 초기화하고(사실 필요없는 작업인 것 같다 → 방문처리를 위에서 해줬으므로)
   4. ans값 갱신

ans값이 상근이를 포함해 갱신되므로, ans > 0 인 경우 ans-1을 리턴해줌

배운점 또는 느낀점

BFS에서 요구하는 정답 갱신하는 부분 잘 생각하기!