[BOJ] 13023. ABCDE(Python) / DFS

www.acmicpc.net/problem/13023

13023번: ABCDE

깔끔한 DFS 문제였다.

• input 받으면서 정점별로 갈 수 있는 정점의 정보를 딕셔너리에 담는다.
• 전역변수 flag를 두어 depth가 4이상 되면 1로 바꿔주며 return하여 더이상 진행하지 않는다.
• 모든 정점에서 start할 수 있다.
• visited로 아직 방문하지 않는 곳에 방문체크하며 다음 재귀로 넘어간다.
• 재귀 풀려 나올 땐 방문체크한 것을 0으로 돌려 놓는다.
• flag가 1이면 1, 0이면 0을 출력한다.

 

파이썬 코드는 다음과 같다.

---

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000)		# 최대 재귀 깊이 1000으로 설정

def dfs(depth, start):
    global flag
    if depth >= 4:
        # print(visited)
        flag = 1
        return
    for next in info[start]:
        if visited[next]:
            continue
        visited[next] = 1
        dfs(depth+1, next)
        visited[next] = 0

# main
N, M = map(int, input().split())
info = {i: [] for i in range(N)}	# 연결정보
for _ in range(M):
    a, b = map(int, input().split())
    info[a].append(b)
    info[b].append(a)

visited = [0] * N
flag = 0
for start in range(N):
    visited[start] = 1
    dfs(0, start)
    visited[start] = 0
    if flag:
        break
if flag:
    print(1)
else:
    print(0)

---

• 시간 : 604ms / 메모리 : 125336KB
• 고찰 : 문제 이해가 좀 헷갈렸다,, 결국 depth가 4 이상일 때 리턴하는 간단한 DFS 문제였다.