[백준] 5567번 - 결혼식

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

 

✔️ 문제

 

 

문제는 다음과 같다.

 

 

✔️ 풀이

 

 

문제와 예제를 살펴보면 1번 노드와 연결된 친구와 친구의 친구까지 결혼식에

참여한다고 한다. 즉, 연결된 노드여도 친구 혹은 친구의 친구가 아니라면

카운트를 세지 않아야 한다.

 

예제 1번을 보게 되면,

 

 

1번 상근이의 친구인 2번과 3번, 친구 3번의 친구인 4번까지 결혼식에

참여하기 때문에 총 2, 3, 4인 3명이 결혼식에 오게 된다.

 

예제 2번을 보게 되면,

 

 

상근이는 친구가 없기 때문에 연결된 노드가 없고,

0명이 결혼식에 오게 된다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
chk = [0] * (n+1)
cnt = 0

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

for i in range(n+1): graph[i].sort()

for i in graph[1]:
  if not chk[i]:
    chk[i] = True
    cnt += 1

  for k in graph[i]:
    if not chk[k]:
      chk[k] = True
      cnt += 1

if not cnt: print(cnt)
else: print(cnt-1)

 

m개 줄에 주어지는 a와 b가 친구이며, b와 a가 친구이기 때문에

각 a와 b 인덱스에 추가해주어야 한다.

 

상근이는 1번 인덱스이기 때문에 1번 인덱스를 돌면서

인덱스에 들어있는 바로 가까운 친구를 탐색하고,

다음 들어있는 친구들을 탐색하면서 (2번째 for문)

친구의 친구를 탐색한 뒤 탐색하면 cnt에 1씩 추가해준다.

 

친구가 없다면 바로 cnt를 출력하면 되지만,

해당 cnt는 본인 1을 포함하기 때문에 -1만큼을 출력해준다.

 

화이팅 💪