[백준/Python] 5567. 결혼식

※ 문제

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

 

 

※ 문제 유형

그래프 이론, 그래프 탐색, 너비 우선 탐색(SILVER_2)

※ 나의 풀이

• 그래프 활용 (인접 리스트)
  • 주어진 친구 관계를 그래프 형태로 저장
  • 각 노드는 사람을, 각 간선은 친구 관계
• 상근이의 직접 친구 리스트(friend) 생성
  • 상근이(1번 노드)의 친구 목록을 graph[1]을 이용
  • 이를 기반으로 직접 친구 리스트 friend를 작성
• 상근이의 친구의 친구 리스트(friend_2) 생성
  • 상근이의 직접 친구를 순회하며, 각 친구의 친구를 확인
  • 상근이 자신(1번)과 이미 직접 친구인 사람은 제외하고, 친구의 친구 리스트에 추가
• 최종 결과 계산
  • 직접 친구와 친구의 친구 수를 합산하여 출력

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())

graph = [[] for _ in range(N + 1)]

for _ in range(M):
    a, b = map(int, sys.stdin.readline().split())

    graph[a].append(b)
    graph[b].append(a)

# 상근이(1)의 친구
friend = [0] * (N + 1)

# 상근이의 학번이 1이므로 graph 1의 해당하는 친구를 체크
for i in graph[1]:
    friend[i] = 1

# 상근이(1)의 친구의 친구
friend_2 = [0] * (N + 1)

# 이미 상근이(1)과 친구인 사람들은 제외
for i in range(1, N + 1):
    if friend[i] == 0:  # 상근이(1)의 친구가 아니면 스킵
        continue
    
    # 상근이(1)의 친구인 사람(i)의 친구들을 탐색
    for j in graph[i]:
        if j != 1 and friend[j] == 0: # 상근이 자신이 아니고, 상근이와 직접 친구가 아닌 경우
            friend_2[j] = 1

print(sum(friend) + sum(friend_2))