파이썬 / BOJ / 7562번 (나이트의 이동)

문제

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

입력

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

각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 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

 

 

풀이

 

우선 해당문제는 BFS를 통하여 접근하여 풀도록 하였다. 위 조건의 이동은 한칸씩 움직이는 것이 아닌, 위 그림의 가운데 좌표를 기점으로 옮겨질 수 있는 방향의 경우의 수를 모두 고려하여 dirs 리스트 배열내에 튜플로 저장하였다.

 

사실 이 문제는 처음 풀었을 때 자꾸 에러가 났다. 그 이유는 27번째 줄 때문이다. 기존에 내가 chess 좌표판(2차원 배열)을 초기화 해줄 때 [[0] * k ] * k 를 이용하여 초기화 해줬다. 하지만 해당 방법으로 초기화를 하게 되면 [0]*k 가 같은 object로 인식하게 되어(같은 id값을 같게 됨) 문제가 발생한다. 그렇기 때문에 chess[0]과 chess[1]는 같은 id값을 갖게 되어 chess[0]를 바꾸면 chess[1]도 값이 바뀌는 현상이 일어나게 된다. 이러한 이유는 주소만 복사하게 되는 얕은 복사가 일어났기 때문이다.

 

이런 경우를 해결하기 위해서는 list comprehension을 이용하여 새로운 객체를 가르키게 함으로  해결이 된다.

import sys
from collections import deque

dirs = [(-1,-2),(-2,-1),(-2,1),(-1,2),(1,-2),(2,-1),(2,1),(1,2)]
#움직이는 방향 리스트

def bfs(x,y,dx,dy):
    queue = deque()
    queue.append((x,y))
    chess[x][y] = 1
    while queue:
        cx, cy = queue.popleft()
        if cx == dx and cy == dy : # 현재 좌표가 목표하는 좌표와 같은지
            print(chess[dx][dy]-1)
            return
        for mov in dirs :
            nx, ny = cx+mov[0], cy+mov[1]
            if 0<= nx < k and 0<= ny < k and chess[nx][ny] == 0:# 다음 좌표가 유효한 좌표내에 있는 지와 아직 방문하지 않은 좌표인지
                chess[nx][ny] = chess[cx][cy]+ 1
                queue.append((nx,ny))
                
N = int(sys.stdin.readline())
for _ in range(N):
    k = int(sys.stdin.readline())
    sx, sy = map(int, sys.stdin.readline().split())
    dx, dy = map(int, sys.stdin.readline().split())
    chess = [[0]*k for _ in range(k)]
    bfs(sx, sy, dx, dy)