[Seop's의 코드풀이] 백준 7562 나이트의 이동 - Python

이번에 풀어 볼 문제는 백준 7562번인 나이트의 이동 이란 문제입니다.

문제는 다음과 같습니다.

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

7562번: 나이트의 이동

 

문제를 정리하자면 

체스판의 크기와 현재 나이트의 위치가 주어집니다.
나이트가 도달하고자 하는 칸이 주어집니다.

 

체스의 규칙을 알고 있는 분이라면 문제는 충분히 이해 했을 것이라 생각돕니다.

저는 본 문제를 너비우선 탐색 알고리즘을 활용해서 풀었습니다.

 

문제 풀이에 관한 아이디어

1. 주어진 체스판의 크기에 맞춰 모든 원소가 0인 board 배열을 만듭니다. 

2. 현재 나이트의 위치에서 이동 할 수 있는 곳을 검색합니다.

3. 이동한 곳의 위치에 1을 더해 board 배열을 업데이트 합니다.

3-1. 이때 이동할 board 배열의 원소가 0이 아닐때만 3의 행동을 취합니다.(같은 곳에 여러번 이동하는 것 방지)

4. 이동한 곳의 위치가 최종적으로 도달하고자 한 곳이라면 목표 위치의 board 값을 출력합니다.

 

좀 더 이해하기 쉽게 그림으로 표현하자면

위 그림처럼 한 변의 길이가 4인 체스판이고

초기위치는 (0,0) 목표위치가 (3, 2) 이라고 한다면

오른쪽 판처럼 이동한 위치와 해당 되는 위치의 최소 이동 횟수를 알 수 있습니다.

 

전체 코드는 다음과 같습니다.

import sys
input = sys.stdin.readline

def soluction() :
    #  나이트가 이동 할 수 있는 방향 정의
    dx = [1, 2, 2, 1, -1, -2, -2, -1]
    dy = [-2, -1, 1, 2, 2, 1, -1, -2]

    I = int(input())
    board = [[0 for _ in range(I)] for _ in range(I)]
    st_x, st_y = map(int, input().split(" "))
    ed_x , ed_y = map(int, input().split(" "))

    #  처음위치와 목표위치가 같다면 0을 리턴
    if st_x == ed_x and st_y == ed_y :
        return 0
    #  처음 bfs에 들어가 있는 값은 현재 위치의 값이다.
    bfs =[[st_y, st_x]]
    while True :
        buf = []
        for y, x in bfs :
            for i in range(8) :
                #  체스판을 안벗어 나는지 확인!
                if x + dx[i] >= 0 and x + dx[i] < I and y + dy[i] >= 0 and y + dy[i] < I :
                    tx = x + dx[i]
                    ty = y + dy[i] 
                    if board[ty][tx] == 0 :
                        board[ty][tx] = board[y][x] + 1
                        buf.append([ty, tx])
                    if tx == ed_x and ty == ed_y :
                        return board[ed_y][ed_x]
        bfs = buf
    
T = int(input())
for _ in range(T) :
    print(soluction())

코드에 대한 피드백은 언제나 감사드립니다.

 

감사합니다.