[백준] 5567. 결혼식 (Python)

이번에 풀어 볼 문제는 <백준 5567번. 결혼식>이다.

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

 

📌 문제 탐색하기

목표

• 상근이가 결혼식에 초대할 사람의 수 구하기

해야 할 것

1. 친구 관계를 어떻게 저장할까?
2. 상근이와 2 개 간선 이내로 연결된 동기는 총 몇명인지 구하기

입력

• n : 전체 동기의 수 ( 2 ≤ n ≤ 500 ) = 정점의 개수
• m : 리스트의 길이 = 관계의 개수 = 간선의 개수 
• ai bi : 친구 관계 쌍 = 간선

아이디어

•  친구 관계를 어떻게 저장할까?
  
  • 딕셔너리를 활용한 인접 리스트 ( 0번 인덱스에는 [] 저장하기 )
• 상근이와 연결된 동기는 총 몇 명인지 구하기 
  • 상근이(1번)를 시작 노드로 하여, BFS 로 탐색 진행  
    ➡️ 2개의 간선 이내로 방문 가능해야 한다는 조건이 있기 때문에 최단거리를 보장하는 BFS로 탐색을 진행한다. (DFS는 최단거리 보장 x)
  • 2개의 간선 이내로 방문 가능한 노드의 수가 곧 결혼식에 초대할 사람의 수

📌 코드 설계하기

1. input을 받고 딕셔너리를 활용한 인접리스트 형태로 관계 graph 저장, 0번 인덱스에는 [] 을 저장하여 원소의 개수는 n+1개

2. BFS 함수를 구현, 큐에 넣을 때마다 깊이를 (cur_v, depth) 형태로 같이 추적

3. 깊이가 2인 노드들이 큐에 모두 들어오면 더 이상 탐색을 진행할 필요 없음.

3. 1번을 시작노드로 하여 DFS 실행, depth=0 으로 초기화

4. len(visited) -1 출력

📌 정답 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)

n = int(sys.stdin.readline()) # 동기의 수
m = int(sys.stdin.readline()) # 간선의 수 == 관계의 수

graph = {i:[] for i in range(n+1)} # 0~ n

for _ in range(m):
    a, b = map(int,sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)


def bfs(start,depth,visited=[]):
    visited.append(start)
    queue = deque()
    queue.append((start,depth))
    while queue: 
        cur_v, cur_depth = queue.popleft() # 큐에서 꺼내 다음 방문할 곳 탐색
        # 현재 깊이가 2라면, 더이상 탐색을 진행할 필요 없음.
        if cur_depth == 2:  
            break
        for next_v in graph[cur_v]:
            if next_v not in visited:
                queue.append((next_v,cur_depth+1)) 
                visited.append(next_v) 
                
                
    return visited

result = bfs(1,0)
print(len(result)-1)

📌 알게 된 것

• BFS 는 최단 거리를 보장하지만, DFS는 최단 거리를 보장해주지 않는다.
• 깊이를 같이 추적하는 로직 기억해두기
  • 큐에 (현재노드, 깊이)의 튜플형태로 저장
  • 큐에 저장된 노드들이 현재까지 탐색을 완료한 노드이므로, 깊이 제한을 넘어가면 더 이상 탐색을 진행할 필요 없다는 아이디어를 떠올리는게 엄청 오래 걸렸다.. 한 번 했으니 기억해두자.