Skip to main content

7562 - 나이트의 이동

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

풀이 키워드​

스포주의

BFS


풀이 코드​

info
  • 메모리: 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 (코드 하이라이트 참고)