[백준 13023번] ABCDE (Python/파이썬)

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

13023번: ABCDE

백트래킹을 이용하는 문제이다.

재귀함수의 작동원리를 완벽하게 알지 못하다면 디버깅을 통해서 한번 코드가 어떻게 작동되는지 확인하면 좋을거 같다.

백트래킹의 좋은 예시로 미로가 있는데, 길을 찾다가 막다른 길이 나오면 다시 갈림길로 돌아가서 다른 방향으로 가야한다.

그때 다시 갈림길로 돌아가는 것을 백트래킹과정이라고 하면 이해하기 쉽다.

 

문제의 경우에는 친구의 연결관계를 찾다가 5명이 연결되기 전에 끊기면 끊기기 한단계 전 친구로 돌아가서 끊기는 쪽말고 다른 친구와 연결해봐야하는데 이 과정이 백트래킹 과정이다.

그러다가 계속 5명이 연결이 안되서 맨 처음까지 오면 시작하는 친구를 바꿔야한다. (이 과정 또한 당연히 백트래킹)

 

우선 각각의 친구가 누구와 연결되어있는지 알기 위해 연결리스트를 만들고, DFS로 탐색하면서 5명이 연결되면 바로 프로그램을 종료하고 도중에 끊기면 백트래킹과정을 수행한다.

한번 지나간 구간을 표시하기 위한 리스트로 만들어 T,F로 저장하였다.

코드는 다음과 같다.

 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
N, M = map(int,input().split())
connect = [[] for _ in range(N)]
way_point = [False]*N
depth = 1

## 친구 관계 리스트 생성
for _ in range(M):
  a, b = map(int,input().split())
  connect[a].append(b)
  connect[b].append(a)

## 재귀 돌리기
def DFS(f):
  global depth
  if depth == 5:
    print(1)
    sys.exit()

  way_point[f] = True
  for i in connect[f]:
    if not way_point[i]:
      depth += 1
      DFS(i)
      ## 한번 지나간 구간 초기화(백트래킹)
      depth -= 1
      way_point[i] = False


for i in range(N):
  DFS(i)
  ## 백트래킹
  way_point[i] = False
print(0)

 

 

 

글에대한 조언 및 질문 모두 환영합니다!