[백준 파이썬] # 7562 나이트의 이동

Silver II

# 7562 나이트의 이동

링크 : https://www.acmicpc.net/problem/7562

7562번: 나이트의 이동

 

풀이

from collections import deque

def bfs(x, y):
    if (loc_x, loc_y) == (des_x, des_y):
        return 0

    else:
        q = deque()
        q.append((x, y))

        dx = [1, 2, 2, 1, -1, -2, -2, -1]
        dy = [2, 1, -1, -2, -2, -1, 1, 2]

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

            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]

                if 0<=nx<l and 0<=ny<l:
                    if chess[ny][nx] == 0:
                        chess[ny][nx] = chess[y][x] + 1
                        q.append((nx,ny))

        return chess[des_y][des_x]


n = int(input())
for i in range(n):

    l = int(input())
    chess = [[0] * l for i in range(l)]

    loc_x, loc_y = map(int, input().split())
    des_x, des_y = map(int, input().split())

    print(bfs(loc_x, loc_y))

 

풀이 방법

• 이전까지의 BFS 풀이와 유사하다. 단, 탐색해야 하는 방향이 8개로 늘어났을 뿐이므로 조심스레 풀어가면 된다

 

후기

• 구름 level이란 곳의 채점 시스템이 백준보다 훨씬 편하다.
• n개의 테스트 셋을 하기 전에 1개만 가지고서 확인하는 지혜를 발휘하자.
• 가뭄속에 단비같은 정답이다 ㅜ..