[Python][백준/BOJ] 5567번 : 결혼식

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

5567번: 결혼식

 

내 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
visited =[0 for _ in range(n+1)]
acq =[[]*(n+1) for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    acq[a].append(b)
    acq[b].append(a)
    
visited[1] = 1
def dfs(i, depth):
    if depth == 2:
        return
    for j in acq[i]:
        if not visited[j]:
            visited[j] = 1
        dfs(j, depth +1)
        
        
dfs(1, 0)
visited[1] =0
print(sum(visited))

 

코드 리뷰, DFS

해당 문제는 길게 적혀있지만, 읽어보면 두 가지의 조건을 충족하는 것의 개수를 출력하는 문제이다.

1. 1과 연결되어 있다.
2. 깊이가 2 이하이다.

그래서 BFS 로 푸는 것이 더 편한 문제이다. 하지만 나는 처음에 문제를 보고 1을 타고 가면서 depth 가 2 이하인 것만 찾으면 되지 않을까 싶어서 DFS로 풀었다.

 

DFS 함수

visited[1] = 1

def dfs(i, depth):
    if depth == 2:
        return
    for j in acq[i]:
        if not visited[j]:
            visited[j] = 1
        dfs(j, depth +1)

우선 1이 주인공인 상근이이므로 1부터 출발한다. 그러므로 1은 방문했다고 표시해놓고 시작한다.

그리고 depth 가 2이면 해당 메모리를 반환한다. 메모리를 반환하면 곧바로 for문으로 넘어가서 j에 1을 더한 수로 진행한다.

만약 입력이 이렇게 된다고 하자.

i	1	2	1	2	3	1
depth	0	1	2	1	2	0
j	2	1	return	3	return	3

그렇다면 DFS 진행은 이렇게 된다. 

acq[i]만 확인하므로 1과 연결되어 있는 수를 다 검사하면 함수는 더이상 다른 수를 체크하지 않고 넘어간다.

조건 자체가 depth가 2 미만일 때만 방문하는 것이므로, 방문했다는 것은 곧 결혼식에 초대한다는 것이다.

그래서 방문하면 1을 저장하고, 1을 총 더한 값이 결과값이다.