less than 1 minute read

문제

접근 방법

문제 설명 그대로 a->b->c->d->e가 가능하다면 1을 출력하는 문제이다.

최단 거리보다는 경로를 찾는 문제이므로 dfs를 사용해야겠다는 생각이 들었다. 시작 노드에서 dfs를 하였을 때, 4번 이동하는 것이 가능하다면, a->b->c->d->e가 가능하다는 뜻이므로 이때 dfs를 종료시켰다.

제일 중요한 것이 임의의 시작 노드에서 dfs를 하였는데 4번 이동이 불가능하여 종료되지 않고 계속 진행될 때, 그 시작노드를 미방문 처리를 해야지 모든 경우의 수를 볼 수 있게 된다는 것이다. 즉, backtracking을 구현해야지 더 빠르면서도 모든 경우의 수를 탐색하는 것이 가능하다.

정답 코드

import sys
input = sys.stdin.readline

'''
각 사람에 대해 dfs로 4번 이동 가능한지 보는 방법
'''

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

possible = False

visited = [False]*(n+1)

def dfs(start, moved):
  global possible
  if possible:
    return
  #재귀 종료 조건
  if moved == 4:
    possible = True
    return

  visited[start] = True
  
  for adj in graph[start]:
    if not visited[adj]:
      dfs(adj, moved+1)

  # start 노드를 거쳐서 정답을 찾지 못했다면 취소 (backtracking)
  visited[start] = False


for i in range(n):
  if graph[i]:
    dfs(i,0)
  if possible:
    break

if possible:
  print(1)

else:
  print(0)

배운 점

나는 백트래킹과 DFS를 못한다.

You May Also Enjoy