[BOJ] #7562 나이트의 이동

나이트의 이동

백준 #7562

---

📌 문제

예제 입력

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

예제 출력

5
28
0

---

📌 풀이

Logic

• 테스트 케이스 수 T 입력 받기
  • 체스판의 크기 I 입력 받기
  • 나이트의 현재 위치 / 이동하려는 위치 좌표쌍 입력 받기
  • BFS 함수 구현 (deque)
    • 현재 위치에서 8방향 이동 가능 여부 확인
    • 이동 가능한 경우 해당 라운드 board에 표기

# 변수명
T : 테스트 케이스 수
I : 체스판의 크기
start_x, start_y : 나이트의 현재 위치 좌표쌍
end_x, end_y : 나이트의 이동하려는 위치 좌표쌍

dq : 현재 나이트의 위치를 저장하는 deque(해당 라운드 출발 지점)
visited : 백트래킹을 위한 리스트 (이미 방문한 노드로는 이동하지 않음)

Python

import sys
from collections import deque

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

def bfs(start_x, start_y, end_x, end_y):
    dq = deque()
    dq.append((start_x, start_y))

    visited[start_x][start_y] = True
    board[start_x][start_y] = 0

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

        if ((x == end_x) and (y == end_y)):
            print(board[x][y])
            return

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

            if ((0 <= nx < I) and (0 <= ny < I)):
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    board[nx][ny] = board[x][y] + 1
                    dq.append((nx, ny))

T = int(sys.stdin.readline())

for _ in range(T):
    I = int(sys.stdin.readline())

    board = [[0] * I for _ in range(I)]
    visited = [[False] * I for _ in range(I)]

    start_x, start_y = map(int, sys.stdin.readline().split())
    end_x, end_y = map(int, sys.stdin.readline().split())

    bfs(start_x, start_y, end_x, end_y)

---

✏️ 새로운 내용

-

---

📚 회고

💡 Solved.ac

• 드디어 골드를 달성했다.
• 또한 이번 문제로 BFS에서 다음 유형으로 넘어가려고 한다.
• 연속 스트릭도 200일을 앞두고 있는데, 학기 중에는 사실 문제 및 풀이에 많은 시간을 쏟기 힘들기에 감을 잃지 말자는 정도의 의미에서 낮은 티어의 문제들을 많이 풀었었다. 이제는 해당 난이도도 조금 올려도 되지 않을까 싶다.