7562 나이트의 이동 / DFS, BFS

 

정답

• 나이트가 이동할 수 있는 경우의 수를 처음에 아래와 같이 했더니 오답이 나옴

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

 

• 다른 정답들을 찾아봐도 이해할 수 가 없어서 시계방향대로 이동할 수 있는 경로를 바꿨더니 정답이 나옴

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

 

• BFS에서 최단 경로 문제를 풀 땐 또는 방향 순서를 안정된 기준(예: 시계 방향) 으로 맞춰줘야 함

from collections import deque
case = int(input())
ans = []
for _ in range(case):
    n = int(input())
    graph = []
    for _ in range(n):
        row = [0] * n
        graph.append(row)

    distance = []
    for _ in range(n):
        row = [0] * n
        distance.append(row)

    start_x, start_y = map(int, input().split())
    goal_x, goal_y = map(int, input().split())

    # 시계방향대로 이동 할 수 있는 수를 둠, BFS에서는 방향 순서를 신경써야 함
    dx = [-2, -1, 1, 2, 2, 1, -1, -2]
    dy = [1, 2, 2, 1, -1, -2, -2, -1]

    def BFS(y, x):
        queue = deque()
        queue.append((y, x))
        graph[y][x] = 1

        while queue:
            y, x = queue.popleft()

            if y == goal_y and x == goal_x:
                return distance[y][x]

            for i in range(len(dx)):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0 <= nx < n and 0 <= ny < n and graph[ny][nx] == 0:
                    distance[ny][nx] = distance[y][x] + 1
                    queue.append((ny, nx))
                    graph[ny][nx] = 1

    ans.append(BFS(start_y, start_x))

for i in ans:
    print(i)