240618 [BOJ/백준] 5567. 결혼식

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

---

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

---

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

---

제출 코드

n = int(input())
m = int(input())
adjl = [[] for _ in range(n+1)]
visited = [-1]*(n+1)
q = []
for _ in range(m):
    i, j = map(int, input().split())
    adjl[i].append(j)
    adjl[j].append(i)

def bfs(num):
    q.append(num)
    visited[num] += 1
    while q:
        x = q.pop(0)
        for i in adjl[x]:
            if visited[i] != -1:
                continue
            visited[i] = visited[x]+1
            q.append(i)

bfs(1)
print(visited.count(1)+visited.count(2))  # 1은 친구를, 2는 친구의 친구를 나타냄

---

결과

---

오늘 SSAFY 취업박람회에서 코드의 최적화도 중요하다는 얘길 들었다. 그래서 다른 사람은 코드를 어떻게 짰을지 궁금해서 시간이 적게 든 코드를 봤는데 덱을 쓰고 가지치기를 적절하게 한 것으로 보였다. 가지치기를 하지 않고 덱을 쓰면 시간이 어떨지 궁금해서 추가했는데 코드도 길어지고 시간도, 메모리도 늘어났다ㅜㅜ

아무튼 이 문제는 예전에 풀어봤던 촌수계산과 유사했다. 그래서 조금 시간이 걸렸지만 성공!ㅎㅎ