[Python] 소프티어 LV.3_순서대로 방문하기

소프티어 LV.3_순서대로 방문하기

bfs : 최단거리
dfs : 가능한 모든 경로. 각 경로별 특징을 기억해야할 때
백트래킹 : dfs랑 비슷해보일 수 있는데 유망한 곳만 추려낸다.

import sys

n, m = map(int, sys.stdin.readline().split())
maps = []
for _ in range(n):
  # 1은 벽, 0은 빈칸
  maps.append(list(map(int, sys.stdin.readline().rstrip().split())))

loc = []
for _ in range(m):
  x, y = map(int, sys.stdin.readline().split())
  # loc을 순서대로 방문
  loc.append([x-1, y-1])



dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


visited = [[0]*n for _ in range(n)]
x, y = loc[0][0], loc[0][1]
visited[x][y] = 1
cnt = 0




def backtrack(x, y, idx):
  global cnt

  # 마지막으로 방문해야하는 칸에 도달 (타겟들을 모두 거쳐 마지막 타겟에 도달)
  if idx == m:
    cnt += 1
    return

  # 타겟에 도달
  if x==loc[idx][0] and y==loc[idx][1]:
    backtrack(x, y, idx+1)
    return
    
    
  for i in range(4):
    nx, ny = x+dx[i], y+dy[i]
    if 0<=nx<n and 0<=ny<n:
      if visited[nx][ny]==0 and maps[nx][ny]==0:
        visited[nx][ny] = 1
        backtrack(nx, ny, idx)
        visited[nx][ny] = 0
        

backtrack(x, y, 1) #첫번째 칸은 이미 타겟. idx는 방문해야할 loc의 다음 인덱스를 가리킨다.
print(cnt)