백준 13023 | ABCDE | python 풀이

문제

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

13023번: ABCDE

BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.

오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.

• A는 B와 친구다.
• B는 C와 친구다.
• C는 D와 친구다.
• D는 E와 친구다.

위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.

내 답안

import sys
from sys import stdin as s
sys.setrecursionlimit(10**6)

result = 0
n, m = map(int, s.readline().split())
network = [[] for _ in range(n)]
visited = [False] * n

for _ in range(m):
    a,b = map(int, s.readline().split())
    network[a].append(b)
    network[b].append(a)

def dfs(start, cnt):
    global result
    visited[start] = True
    cnt +=1
    
    if  cnt == 5:
        result = 1
        return 
    
    for f in network[start]:
        if visited[f] == False :
            visited[f] = True
            dfs(f, cnt)
            
    visited[start] = False
    
for i in range(n):
    if result == 1 :
        break
    dfs(i, 0)
    
print(result)

해설

DFS 재귀로 해결하였다.
DFS가 소위 "한 놈만 노리는(?)"특징을 갖고 있기 때문에, 특정 노드에서 시작하여 깊이를 카운트하며 탐색을 수행한다. 이때 깊이 변수(cnt)가 5에 도달하면, 문제에서 주어진 ABCDE 관계가 성립하기 때문에, 정답 변수(result)에 1을 대입한다.

 

피드백

DFS 재귀에서 특정 노드에서 출발하여 최대의 깊이에 도달할 때를 파악하는 데 시간이 걸렸다. 노드가 최대 깊이에 도달했음에도 깊이 5보다 작다면 마지막 노드의 방문 기록을 없애는 아이디어도 어렵게 떠올렸다.. 재귀와 함수 호출 스택의 개념을 오래만에 생각해내려고 하니까 헷갈리는 부분도 있었고..