[Softeer] [HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

문제링크

---

[HSAT 7회 정기 코딩 인증평가 기출] 순서대로 방문하기

풀이과정

---

dfs를 이용해서 풀어봤다.

반드시 들러야하는 포인트를 순서대로 방문하게 했고, 만약 해당 포인트들을 다 방문했다면 종료되게 했다.
이동한 점들을 포인트에 전부 추가해서 마지막 점을 기준으로 이동했다.

코드

---

import sys

directions = [[-1, 0], [0, -1], [1, 0], [0, 1]]

n, m = map(int, input().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

targets = []
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    targets.append([x-1, y-1])

def dfs(points, depth):
    if depth == m:
        result.append(points)
        return 
        
    if points[-1] == targets[depth]:
        dfs(points, depth+1)
        return

    x, y = points[-1][0], points[-1][1]
    for dx, dy in directions:
        mx, my = x + dx, y + dy

        if (mx < 0 or n <= mx or my < 0 or n <= my) or maps[mx][my] == 1:
            continue

        if [mx, my] not in points:
            dfs(points + [[mx, my]], depth)


result = []
dfs([targets[0]], 0)

print(len(result))

결과

---