5567

날짜 : 2022. 11. 24

사용 언어 : python

 

문제

 

 

코드

import sys

n = int(sys.stdin.readline())  # 동기의 수
m = int(sys.stdin.readline())  # 리스트의 길이
f = [False] * (n + 1)  # 참석하는 친구
r = [[] for i in range(n + 1)]  # 친구관계
f[1] = True

for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())  # 친구관계 입력
    r[a].append(b)
    r[b].append(a)
#print(r)

def dfs(node, idx):  # idx -> 0 : 본인, 1 : 친구, 2 : 친구의 친구
    if idx > 2: return # 친구의 친구 이상인 경우 리턴
    #print(node, idx)
    for i in r[node]:
        if idx <= 1:  # 본인 or 친구인 기준으로
            f[i] = True  # 친구 or 친구의 친구 참석처리
            dfs(i, idx+1)

dfs(1, 0)
print(f[2:].count(True))
#print(f)

 

 

풀이

- depth를 기록할 파라미터를 동봉한 DFS를 이용해 풀 수 있는 문제였다.

- idx에서 0은 본인, 1은 친구, 2는 친구의 친구를 가리킨다.

- 만약 dfs에서 idx가 3보다 같거나 커진다면 관계가 없는 사람이기 때문에 True처리가 불가능하다.

 

 

알게된 점

- 단순 if문에서 f[i] == False라고 했다가 거쳐가는 경로를 하나 빼먹는 케이스가 나타나는 바람에 꽤 많은 시간을 잡아먹었다.

- dfs나 bfs에서는 재귀의 케이스를 확인하는 디버깅을 통해 좀 더 확실하게 재귀과정을 살펴보아야 할 필요가 있는 것 같다.

 

참고 사이트

-