나이트의 이동 - 7562

1. 개요

원본 문제: https://www.acmicpc.net/problem/7562

2. 코드

from collections import deque

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

t = int(input())
for _ in range(t):
    l = int(input())
    start_pos = list(map(int, input().split()))
    dest_pos = list(map(int, input().split()))
    count_graph = [[0] * l for _ in range(l)]
    #count_graph[0][0] = -1

    queue = deque([start_pos + [0]])
    while len(queue) != 0:
        v = queue.popleft()
        y = v[0]
        x = v[1]
        cur_count = v[2]

        if y == dest_pos[0] and x == dest_pos[1]:
            print(cur_count)
            break

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

            if 0 <= nx < l and 0 <= ny < l:
                if count_graph[ny][nx] == 0:
                    count_graph[ny][nx] = cur_count + 1
                    queue.append([ny, nx, cur_count + 1])

3. 코멘트

그냥 BFS 문제인데, 주석 부분 (count_graph[0][0] = -1) 때문에 30분을 낭비했다. 시작지점이 [0][0]일 거라는 보장은 없다. '다시 방문할 필요가 없다' 는 이유로 -1로 설정하는 논리 자체는 틀리지 않았지만, 시작지점이 다른 경우를 고려하지 못했던 탓에 틀렸던 문제.

잠이 덜 깼었나 보다.