[Softeer](LV 3) 순서대로 방문하기

문제 링크

LV 3: 순서대로 방문하기

구현 방식

• dfs로 풀어주었다
• "순서대로 방문"하도록 하기 위해 check 변수를 이용했다. check은 다음 도달해야할 칸의 index이다

코드

import sys

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

N, M = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for n in range(N)]
mid = []; mid_set = set(); mid_dict = dict()
for m in range(M): x, y = map(int, sys.stdin.readline().split()); x -= 1; y -= 1; mid.append((x, y)); mid_set.add((x, y)); mid_dict[(x, y)] = m

def dfs(x, y, check):
    global answer
    if check == M and (x, y) == (mid[-1][0], mid[-1][1]):
        answer += 1
        return

    for i in range(4):
        nx = x + dx[i]; ny = y + dy[i]
        if 0<=nx<N and 0<=ny<N and board[nx][ny] == 0 and not visit[nx][ny]:
            if (nx, ny) in mid_set: #mid에 있는 칸인 경우
                if mid_dict[(nx, ny)] == check:
                    visit[nx][ny] = True
                    dfs(nx, ny, check+1)
                    visit[nx][ny] = False
            else:
                visit[nx][ny] = True
                dfs(nx, ny, check)
                visit[nx][ny] = False


answer = 0
visit = [[False]*N for n in range(N)]; visit[mid[0][0]][mid[0][1]] = True
dfs(mid[0][0], mid[0][1], 1)
print(answer)