백준 - ABCDE(13023)

문제 링크 ▶︎ 백준 ABCDE 13023

문제 파악

N (5 ≤ N ≤ 2000), M (1 ≤ M ≤ 2000) 이라는 조건으로 인해 전체를 순회하는 반복문안에 함수를 집어넣어서 풀어야겠다고 생각했다.

A는 B와 친구다. B는 C와 친구다. C는 D와 친구다. D는 E와 친구다. 이라는 말은 즉 DFS로 접근하되 depth 가 5인 경우 return 하면 될 것 같다.
그래서 DFS 함수안에서 그걸 체크하는 로직도 넣어둬야 할 것 같다.
boolean 으로 flag를 줘서 flag가 변하면 모두 return 해서 함수를 모두 종료시키고 답을 출력하는 식으로 풀어야겠다.

접근 방법

문제에서 친구 관계를 나타내는 것은 해시 딕셔너리에 집어넣었고, 쌍방향으로 입력해줬다.
그리고 stop이라는 boolean 변수를 만들고 dfs 함수의 dep==5 조건을 만족하면 dfs함수를 모두 종료시키도록 만들었다.

dfs함수에서는 stop 글로변 변수를 선언하고 하나의 인덱스를 받아서 해당 노드와 친구인 노드를 모두 탐색한다. 그리고 재귀함수로 dep+1로 넘겨준다. 만약 이미 모두 방문한 노드이거나 친구인 노드가 없다면 해당 노드의 방문을 취소해줘야한다. 그래야지 그 전의 dfs로 넘어가서 다른 노드를 방문하기 때문이다.

만약 dep==5에 도달한다면 우리는 stop 변수를 True로 변경해주고 해당 dfs함수를 리턴해준다. 그렇다면 그 전의 dfs함수들에서는 if stop: 조건에 걸려서 모두 리턴하게 된다.

이러한 dfs 함수를 노드마다 검사해주다가 stop변수를 만족하게 되면 1을 출력하고 전부 다 돌아도 stop변수를 만족하지 못한다면 0을 출력하게 된다.

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(i,dep):
    global stop
    if stop:
        return 
    if dep == 5:
        stop = True
        return
    visit[i] = 1
    for val in maps[i]:
        if visit[val] == 0:
            dfs(val,dep+1)
    visit[i] = 0
    
n, m = map(int, input().split())
maps = {i:[] for i in range(n)}

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

stop = False
visit = [0] * n
for i in range(n):
    dfs(i,1)
    if stop:
        break

if stop:
    print(1)
else:
    print(0)

개선 사항

A,B,C,D,E 의 관계라는 예시가 dep=5라는 것을 깨닫는 데 조금의 시간을 소요했던 것 같다. 그리고 처음에는 방문할 곳이 없을 때, 해당노드를 원상복귀시키지 않아서 틀린 답이 나왔는데 이러한 부분에 대해서 더 잘 생각하고 문제에 접근해야겠다.