[백준] 13023번 ABCDE - DFS 풀이 + 반례 (Python3)

문제와 입출력

제한 조건과 설계

제한 조건

1. N이 2000이하이므로 DFS를 쓸 수 있음.
2. 무방향 그래프.
3. 시간 제한과 메모리 제한도 넉넉하다.
4. DFS 탐색으로, 문제의 조건을 만족 시켜야 한다.

---

자연어 알고리즘

1. 그래프 생성, 방문 테이블, 노드 목록 생성
2. 각각의 노드를 시작 지점으로 DFS 탐색
3. DFS 탐색
   • 1) 탐색 노드 방문 처리 후, route에 탐색 노드 push
   • 2) route의 길이가 5이면 -> 1을 출력하고 종료
   • 3) 인접 노드 중 아직 방문하지 않은 노드가 있다면 -> 그 인접 노드로 DFS 탐색
   • 4) 인접 노드 모두를 방문했다면 -> route에서 현재 탐색 노드를 pop 한 뒤, 미방문 처리
4. 1 ~ 3 이 종료될때 까지 반복
5. 0 출력 후 종료( ABCDE 관계가 나왔다면 3-(2)에서 종료)

---

코드

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

n,m = map(int, input().split())
nodes = [n for n in range(n)]
graph = [[] for _ in range(n)]

for i in range(m):
    u,v = map(int, input().split())
    graph[u].append(v)
    graph[u].sort()
    graph[v].append(u)
    graph[v].sort()

def dfs(graph, i, visited, route):
    visited[i] = True
    route.append(i)
    if len(route) == 5:
        print(1)
        exit()

    for j in graph[i]:
        if not visited[j]:
            dfs(graph,j,visited,route)
    
    visited[route.pop()] = False

for i in nodes:
    visited = [None] * (n)
    dfs(graph,i,visited, [])

print(0)

---

(반례) 이미 방문된 노드가 나중에 재방문 될 것을 대비하여 방문을 미방문으로 처리

내 문제를 해결해 준 반례

필자 같은 경우에는 인접 노드가 여러 개 일때, 작은 노드를 먼저 방문하는 방식을 택했다. 이 방식에 따르면 이동 경로는 아래와 같다.

(시작: 0) 

0->1

0->1->3

0->1->3->2

0->1->3

0->1

0->1->4

0->1->4->3

0->1->4->3->2 (A-B-C-D-E 관계)

위와 같은 과정으로 문제의 답이 찾아진다.

 

위 그래프에서 1과 같이 인접한 노드가 2개 이상인 경우 그 노드 중 한 노드가 방문됬다 하더라도 나중에 다시 재방문 될 수 있기에 꼭 다시 미방문 처리가 되어야 한다. 예를 들자면, 0->1->3->2 까지 갔다가 더 이상 방문할 곳이 없어 0->1로 되돌아 와서 0->1->4까지 왔을 때 3은 다시 재방문 된다. 이때, 만약 3이 재방문 되는데 이미 방문 처리 되어 있다면 3를 다시 방문하지 못한다. 

따라서, 0->1->3->2에서 0->1->3으로 되돌아 갈때 반드시 2에 대해서 미방문 처리가 되어야 하며, 0->1->3에서 0->1로 되돌아 갈때도 마찬가지로 반드시 3에 대한 미방문 처리가 되어야 한다. 이렇게 해야만 나중에 다른 경로를 통해 2, 3을 재방문 할 수 있다.

---

세 줄 요약

1. 노드를 방문하면, 그 노도는 방문 처리되어야 한다.
2. DFS 탐색 시 이전 노드로 다시 되돌아 갈 때, 방문에서 미방문으로 재설정해야 하는 문제도 있다.
3. 노드와 노드 사이의 연결 관계, 이동 거리 문제는 DFS가 BEST WAY.