[백준 7562] 나이트의 이동

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

---

• 문제설명
  시작 좌표와 도착 좌표가 주어지면 나이트가 최소 몇 번을 이동해야 하는 지를 출력해야 하는 문제이다.
• 제출코드

from collections import deque
import sys

input = sys.stdin.readline

dx = [-2,-1,1,2,2,1,-1,-2] #이동할 수 있는 x좌표
dy = [1,2,2,1,-1,-2,-2,-1] #이동할 수 있는 y좌표

def bfs(l,a,b,c,d):
    map = [[-1]*l for _ in range(l)] #초기에 모든 좌표 -1설정
    map[a][b] = 0 #시작점 0으로 설정
    dq = deque()
    dq.append((a,b))
    while dq:
        x, y = dq.popleft()
        if x == c and y == d:
            return map[c][d]
        for i in range(len(dx)):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<l and 0<=ny<l and map[nx][ny] == -1: #좌표 안에 존재하고 처음 방문하는 좌표일 때
                map[nx][ny] = map[x][y] + 1 #이전의 좌표에 저장된 값에 1씩 더하기
                dq.append((nx,ny))

T = int(input())
for i in range(T):
    l = int(input())
    a, b = map(int,input().split())
    c, d = map(int,input().split())
    answer = bfs(l,a,b,c,d)
    print(answer)

 

• 코드설명
  먼저 나이트가 이동할 수 있는 점을 좌표로 표현에 dx, dy에 저장해 줄 것이다. 만약 왼쪽으로 두 칸, 위쪽으로 한 칸 이동한다면 이는 dx = -2, dy = -1로 표현할 것이다. 
  그리고 체스판의 한변의 길이와 시작점, 도착점을 입력받으면 이를 넘겨서 처리하는 bfs함수를 만들었다.
  이 함수에서는 먼저 모든 좌표를 -1로 초기화할 것이다. 2차원 배열이므로 체스판처럼 l X l크기의 정사각형 모양이 만들어진다고 생각하면 된다. 시작점은 0으로 만들고 deque를 이용해서 시작점을 append 한다.
  이제 dq에서 while문을 돌릴 건데 dq에서 가장 왼쪽 좌표를 pop 해서 이 점과 도착점을 비교한 후 같다면 이 점에 저장된 값을 return 해줄 거다.
  for문을 통해 나이트가 이동할 수 있는 모든 좌표의 경우의 수를 생각할 것이다. 이전의 좌표인 x, y에다가 나이트가 이동할 수 있는 경우의 좌표를 더해서 저장하고 이 좌표가 체스판 크기 안에 존재하고 한 번도 방문하지 않은 좌표라면 이전의 좌표에 저장된 값에 1을 더해 몇 번 이동했는지 세주면 된다. 그리고 현재 좌표를 append 해서 다시 while문을 돌면 된다.

 

---

• 마무리
  좌표문제를 오랜만에 풀어봐서 bfs를 이용해야 하는지 감을 못 잡았는데 풀이를 보면서 같이 생각해 보니 관련 문제를 많이 풀다 보면 익숙해질 것 같다.