[백준] 16948. 데스 나이트 Python

문제 링크 : 16948. 데스 나이트

16948번: 데스 나이트

 

풀이 코드 : GIthub
 

문제

게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다.
데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다.
크기가 N×N인 체스판과 두 칸 (r1, c1), (r2, c2)가 주어진다. 데스 나이트가 (r1, c1)에서 (r2, c2)로 이동하는 최소 이동 횟수를 구해보자. 체스판의 행과 열은 0번부터 시작한다.
데스 나이트는 체스판 밖으로 벗어날 수 없다.
 

풀이

전형적인 BFS문제이다. N*N 행렬을 생성하고 시작점으로부터 방문위치를 기록하며 BFS로 탐색하면 답을 구할 수 있을 것이다.

7*7 체스판의 가운데에서 시작한다고 하면 이동할 수 있는 곳은 그림과 같다.

• 위 그림과 같이 7*7 체스판의 한 가운데서 시작(r1, c1)을 한다고 하면 이동할 수 있는 좌표는 위 그림과 같다.
• 다음으로 위 그림에서 이동한 좌표에서 또 이동할 수 있는 다음 좌표는 아래와 같다.

두 번째로 이동할 수 있는 좌표

• 이제 위 그림에서 더 이동할 수 있는 좌표가 없다.
• 그렇다면 이제 해당 좌표에서 목적지 좌표(r2, c2)의 위치가
  • 흰색(갈 수 없는곳)이라면 답은 -1
  • 주황색(1번만에 간 곳)이라면 답은 1
  • 빨간색(2번만에 간 곳)이라면 답은 2
• 위와 같이 계산할 수 있다.

코드

import sys 
from collections import deque


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

r1, c1, r2, c2 = map(int, sys.stdin.readline().split(' '))

maps = [[0] * N for _ in range(N)]
visited_maps = [[0] * N for _ in range(N)]
visited_maps[r1][c1] = 1
dx = [-2,-2, 0, 0, 2, 2] 
dy = [-1, 1, -2, 2, -1, 1] 
n  = N
m = N

queue = deque()
queue.append((r1, c1))

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

    for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < m and  visited_maps[nx][ny] == 0:
            maps[nx][ny] = maps[x][y] + 1
            visited_maps[nx][ny] = 1
            queue.append((nx, ny))

if maps[r2][c2] != 0:
    print(maps[r2][c2])
else:
    print(-1)

• input을 받는다.
  • N, r1, c1, r2, c2

 

• N * N 의 map과 visited map을 만든다 
• dx, dy에 나이트의 움직임을 저장한다.
• queue에 초기 위치를 저장한다.
• 초기 위치에서 나이트가 갈수 있는 위치로 움직이고 해당 위치가 맵에서 벗어나지 않는지 방문한 곳은 아닌지 확인한다.
  • 갈 수 있다면 해당 위치로 움직이고 maps에 움직인 좌표에 몇 번만에 움직였는지 숫자를 저장한다. 
  • 그리고 방문했다는 표시를한다.
• 갈 수 있는 좌표를 다시 queue에 넣는다.
• 위 과정을 갈 곳이 없을때까지 반복한다.
• 반복이 끝난 후 목적지 좌표에 저장된 수를 출력한다.
• 0이라면(못가는 곳) -1를 출력한다.

결과
 
가볍게 통과했다.
 

 
 
어려웠던점
 
처음에 2차원 배열을 생성하고 값을 저장하는데 다음과 같이 했다.
 

maps = [[0]*7]*7

 
위와 같이 해여도 그냥 보기에 maps에 0으로 된 2차원 배열이 생성되었다.
그런데 아래와 같은 코드를 실행하니
 

maps[0][2] = 3 

[[0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0],
 [0, 0, 3, 0, 0, 0, 0]]

 
이렇게 지정한 index가 아닌 모든 행에 값이 들어가 버렸다.
 
GPT에게 물어본 결과 원인은 다음과 같았다. 

이 코드의 문제는 모든 행이 같은 리스트 객체의 참조를 갖게 되어서 발생합니다. 즉, 당신이 만든 2차원 배

 

열에서 모든 행은 같은 객체를 참조하고 있기 때문에 한 행의 요소를 변경하면, 다른 모든 행에도 동일한 변경이 적용됩니다.

 

이를 방지하기 위해서는 각 행이 고유한 리스트 객체를 참조하도록 2차원 배열을 생성해야 합니다.

 

아래와 같이 for 루프를 사용하여 각 행에 대한 새로운 리스트를 생성할 수 있습니다:

 

visited_maps = [[0]*7 for _ in range(7)]