[백준 13023] ABCDE (with Python / DFS, 백트래킹)

문제링크

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와 친구다.

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

입력

첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.

둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.

출력

문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.

예제 입력 1

5 4
0 1
1 2
2 3
3 4

예제 출력 1

1

예제 입력 3

6 5
0 1
0 2
0 3
0 4
0 5

예제 출력 3 

0

 

문제풀이

스택으로 풀어보려고 했는데 많이 헤맸다.

백트래킹은 재귀함수로 쉽게 구현가능하다고 한다.

 

핵심

1. 모든 노드를 시작점으로 하여 DFS 전부 수행 

  ABCDE 패턴을 DFS를 통해서 하나의 경로만 찾으면 되니까

2. 재귀 호출마다 depth를 더함

3. 백트래킹 (하나의 경로를 DFS 마치면 현재노드의 방문노드 해제하기)

코드

<재귀>로 푼 코드

import sys

sys.setrecursionlimit(10000)
input = sys.stdin.readline

N, M = map(int, input().split())
arrive = False
graph = [[] for _ in range(N)]
visited = [False] * N

#입력값 받아 인접리스트 만들기 (그래프 구현)
for _ in range(M):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

def DFS(cur, depth):
    global arrive
    if depth == 5:    # depth 5가 되면 ABCDE 패턴 찾은것이므로 탐색종료
        arrive = True
        return

    visited[cur] = True
    
    # 현재노드의 친구관계 확인
    for node in graph[cur]:
        if not visited[node]:
            #재귀호출
            DFS(node, depth + 1)  #현재의 경로의 깊이 정보를 DFS함수 매개변수로 넘겨줌

    visited[cur] = False # 백트래킹 (현재노드의 방문노드는 다른 경로로 DFS할때 필요하므로 다시 해제)

# 모든 노드를 시작점으로 해서 DFS 전부 한번씩 수행
for i in range(N):
    DFS(i, 1)
    visited[i] = False
    if arrive:
        break

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

<스택>으로 푼 코드

import sys
import copy
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
visited = [False] * N
arrive = False

for i in range(M):
    n1, n2 = map(int, input().split())
    graph[n1].append(n2)
    graph[n2].append(n1)

def DFS(start):
    global arrive
    stack = [(start, 1, [start])]
    
    while stack:
        cur, depth, path = stack.pop()
        visited[cur] = True
        
        if depth == 5:
            arrive = True
            return
        
        for node in graph[cur]:
            if not visited[node] and node not in path:
                newPath = copy.deepcopy(path)
                newPath.append(node)
                stack.append((node, depth + 1, newPath))
        visited[cur] = False
        
for i in range(N):
    DFS(i)
    if arrive:
        break

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

 

결론

백트래킹 써야하는 경우에는 그냥 재귀함수로 풀자...