7562-나이트의 이동

https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

그래프 탐색 파트의 문제들을 개념부터 차근차근 복기하고 있다. 나이트의 이동은 가장 기본적인 그래프 탐색 문제에서 방향이 8가지로 늘어난것 말고는 다른게 없다. 별다른 제약조건이 없는 상태에서의 최단거리 문제이므로 BFS를 사용했다.

 

문제 유형에 따라 풀이방법을 나름 정형화 시키고 있다. dx, dy 를 쓴다거나 is_possible의 이름으로 배열 체크 함수를 만든다거나.. 확실히 이정도 수준의 문제들은 그냥 쭉 코드를 작성해 나갈 수 있는 정도가 된 것 같다. 이렇게 생각해보니 올해 초와 비교해서 어느정도 실력향상이 있는 것 같아 조금 위안이 된다..

 

import sys
sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(10**6)
from collections import deque

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

def is_possible(x, y):
    global l
    return 0 <= x < l and 0 <= y < l

T = int(input())
for _ in range(T):
    l = int(input())
    x, y = map(int, input().split())
    px, py = map(int, input().split())
    if x == px and y == py:
        print(0)
        continue

    dq = deque()
    chk = [[0 for _ in range(l)] for _ in range(l)]

    dq.append((x,y,0))
    chk[x][y] = 1
    tri = 0
    while dq:
        nowx, nowy, nowcnt = dq.popleft()
        for i in range(8):
            nx, ny = nowx+dx[i], nowy+dy[i]
            if nx == px and ny == py:
                ans = nowcnt+1
                tri = 1
                break
            if is_possible(nx,ny) and chk[nx][ny] == 0:
                chk[nx][ny] = 1
                dq.append((nx, ny, nowcnt+1))            
        if tri:
            break
    print(ans)