백준 7562번 파이썬

문제 링크

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

7562번: 나이트의 이동

 

시간 제한 / 메모리 제한

1 초

256 MB

 

문제

체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

 

입력

입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.

출력

각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.

예제 입력

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

예제 출력

5
28
0

문제 풀이를 위해 생각한 것

1. 테스트 케이스마다 2차원 배열의 체스판 및 같은 크기의 방문 체크 배열을 선언한다.
2. 나이트의 이동 방향으로 설정할 각각 8개의 x, y값이 담긴 dx, dy 튜플을 선언한다.
3. 큐를 선언하고, 현재 위치와 이동 횟수를 큐에 담는다. (x, y, d)
4. 8개의 각각 다른 dx, dy좌표가 탐색 가능한 것인지 확인하고, 가능하다면 (nx, ny, d +1)을 큐에 append한다.
5. q.popleft한 값이 목적지 좌표이면 d값을 출력한다.
6. BFS는 언제나 최단거리를 보장한다. 한 Depth씩 탐색하기 때문.

 

사용한 자료구조 / 알고리즘

2차원 배열 / BFS

 

풀이 코드

from collections import deque
import sys
input = sys.stdin.readline

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


def bfs(sx, sy, ex, ey):
    d = 0
    q = deque()
    q.append((sx, sy, d))

    while q:
        x, y, d = q.popleft()
        if x == ex and y == ey:
            print(d)
            return
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < b and 0 <= ny < b and not visited[nx][ny]:
                visited[nx][ny] = True
                q.append((nx, ny, d + 1))


t = int(input())
for _ in range(t):
    b = int(input())

    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())
    if sx == ex and sy == ey:
        print(0)
        continue
    board = [[0] * b for _ in range(b)]
    visited = [[False] * b for _ in range(b)]
    bfs(sx, sy, ex, ey)

 

시간 복잡도 분석

O(N^2).

최악의 경우 체스판을 모두 밟아야 한다. 따라서 체스판의 크기가 N일 때, O(N^2)의 시간 복잡도를 가진다.

 

문제에서 중요한 부분

다른 BFS, DFS 문제와 유사하나, 방향이 8개인 점과 이동의 최소 횟수를 구해야 하는 점을 고려하며 풀어야 했다.