7562 - 나이트의 이동

정보

• 문제 보기: 7562 - 나이트의 이동
• 소요 시간: 15분 22초
• 풀이 언어: python
• 체감 난이도: 1️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

BFS

풀이 코드

정보

• 메모리: 34096 KB
• 시간: 1856 ms

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

l = 0
endX, endY = 0, 0
dx = [-1, 1, -2, 2, -2, 2, -1, 1]
dy = [-2, -2, -1, -1, 1, 1, 2, 2]
board = [] # visited

def bfs(sx, sy):
    global board
    q = deque()
    q.append((sx, sy))
    board[sx][sy] = 0
    
    while q:
        x, y = q.popleft()
        if x == endX and y == endY:
            return
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < l and 0 <= ny < l and board[nx][ny] == -1:
                board[nx][ny] = board[x][y] + 1
                q.append((nx, ny))


def solution():
    global l, endX, endY, board
    l = int(input())
    startX, startY = map(int, input().split())
    endX, endY = map(int, input().split())
    board = [[-1 for _ in range(l)] for _ in range(l)]
    
    bfs(startX, startY)
    print(board[endX][endY])
    
    
if __name__ == '__main__':
    tc = int(input())
    for _ in range(tc):
        solution()

최단거리이므로 너비우선탐색이 직관적이다.

풀이 해설

list 대신 deque을 사용한 이유?

• 파이썬 위키에 따르면, queue 목적의 사용은 deque이 우월하다.

  If you need to add/remove at both ends, consider using a collections.deque instead.

  (하지만 index로 접근하려면 list를 사용해야 함) [관련하여 흥미로운 레퍼런스]

visited 처리

• 최단거리이므로 왔던 좌표에 다시 올 일이 없다.
• board는 방문 체크의 역할을 수행한다.

메모

• 중간에 return으로 끊어주면 1856 ms, 안하면 3384 ms (코드 하이라이트 참고)