1. 오늘의 문제
오늘은 체스판에서 나이트가 어떤 지점으로 이동하기 위한 최단경로를 찾는 것이었다.
폰이 움직일수 있는 경우의 수가 너무 많기에, 깊이우선탐색을 하면 탐색의 깊이가 너무 깊어진다는 문제가 있었다.
그래서 너비우선탐색으로 문제를 풀어야 했다.
문제
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
2. 고민했던 점
너비우선탐색을 2차원으로 만드는 것은 그리 어렵지 않았다.
이때까지 만들었던 visited 리스트를 판다스처럼 2차원으로 배열하고, xy좌표를 기준으로 위치를 찾으면 그만이었다.
그런데 이전과 같이 list를 하나 만들어 배열을 집어넣으며 깊이를 측정했더니 시간초과가 나왔다.
아마 list를 만들고, 그 list를 다시 deque에 집어넣는 과정에서 많은 시간이 소모된 것 같았다.
다른 사람들을 보니 따로 배열을 만드는 것이 아니라 tuple의 형태로 (x, y, depth)를 바로 deque에다 집어넣어 주었다.
해당 방식으로 하니 쉽게 풀렸다.
3. 코드
from sys import stdin
from collections import deque
put = stdin.readline
tests = int(put())
# test 횟수를 돌면서 입력받음
for test in range(tests):
# 체스판 크기를 받아서 체스판 형태의 리스트를 만듦
plateSize = int(put())
chessPlate = [[0 for x in range(plateSize)] for y in range(plateSize)]
# 현재 위치와 타겟 위치를 표시한
nowXPosition, nowYPosition = map(int, put().split())
targetXPosition, targetYPosition = map(int, put().split())
# 덱으로 que를 만들고 현재 위치와 트리의 깊이를 튜플로 입력함.
que = deque()
que.append((nowXPosition, nowYPosition, 0))
# 나이트가 움직일수 있는 x방향과 y방향을 리스트로 입력함. 이후 zip으로 for문을 돌 예정
moveX = [-2, -1, 1 ,2, 2, 1, -1, -2]
moveY = [1, 2, 2, 1, -1, -2, -2, -1]
# 찾으면 멈추도록 find라는 변수를 설정하고 루프를 돔
find = True
while find:
# 큐에서 가장 좌측에 있는 요소를 꺼내 x, y 좌표와 깊이를 할당함.
xyd = que.popleft()
x = xyd[0]
y = xyd[1]
depth = xyd[2]
# 만일 현재 좌표와 타겟 좌표가 일치하면 반환
if x == targetXPosition and y == targetYPosition:
print(depth)
find = False
break
# 아까 설정한 나이트가 움직일수 있는 모든 방향으로 탐색함.
for addX, addY in zip(moveX, moveY):
changeX = x + addX
changeY = y + addY
# 만일 체스판을 벗어나거나, 방문한 곳이면 그냥 넘어감.
# 그게 아닐 경우 체스판에 1을 표시하고 큐에 집어넣음.
if changeX >= 0 and changeX < plateSize and changeY >= 0 and changeY < plateSize \
and chessPlate[changeX][changeY] == 0 :
chessPlate[changeX][changeY] = 1
que.append((changeX, changeY, depth+1))
4. 느낀점
이때까지 자료형에서 set, list, dictionary를 이용한 적은 많았지만 tuple을 이용한 건 처음이었다.
opencv를 할 때 반환되는 값이 tuple이 있는 것을 많이 보았었는데, 이번에 코드를 만들면서 tuple이 이렇게도 활용될 수 있구나 하는 생각이 들었다.
반환값의 위치가 변하면 안되는 자료에는 list보다 tuple을 쓰는게 더 맞는 것 같다.
그리고..
아기를 재우다가 같이 잠이들어버려서 새벽 4시에 이렇게 글을 쓴다.
하루에 하나씩 글을 쓴다는게 정말 쉽지 않음을 실감한다.
