[백준] 7562 - 나이트의 이동 [Python(파이썬)]

문제

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

풀이

최단 거리와 관련된 그래프 탐색 문제는 너비 우선 탐색(BFS)를 통해 해결한다.

큐에 좌표(y,x)와 함께 이동횟수(cnt)를 함께 삽입하여 탐색시 1씩 증가하게 한다.

만약 이동하려는 칸의 좌표에 도달하면 이동횟수를 출력하고 탐색을 종료한다. 

코드

import sys, collections

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

def bfs(cur, target):
    q = collections.deque([])
    q.append(cur+[0]) # 0 == cnt
    visited[cur[0]][cur[1]] = 1

    while q:
        y, x, cnt = q.popleft()
        if y == target[0] and x == target[1]:
            print(cnt)
            break

        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < l and 0 <= nx < l: 
            	if not visited[ny][nx]:
                	visited[ny][nx] = 1
                	q.append([ny, nx, cnt + 1])


n = int(sys.stdin.readline().strip())

for _ in range(n):
    l = int(sys.stdin.readline())
    visited = [[0 for _ in range(l)] for _ in range(l)]
    cur_pos = [int(x) for x in sys.stdin.readline().split()]
    target_pos = [int(x) for x in sys.stdin.readline().split()]

    bfs(cur_pos, target_pos)