[Algorithm] 백준 7562 나이트의 이동 | 파이썬 BFS

※ 7562 나이트의 이동

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

 

문제 해결 TIP

bfs로 간단하게 풀 수 있다. 기존의 문제들은 상하좌우로 움직일 수 있지만 이 문제는 대각선으로 8방향 이동할 수 있다. 이에 맞춰서 dx, dy를 재설정해준다. 이후 최단거리 문제와 비슷하게 1씩 추가해가며 이동량을 그래프에 저장한다. 목표 좌표에 도달하면 이동량을 출력한다.

 

전체 코드

from collections import deque

n = int(input())
for i in range(n):
    l = int(input())
    graph = [[0]*l for _ in range(l)]
    i, j = map(int,input().split())
    r, c = map(int,input().split())
    graph[r][c] = -1

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

    def bfs(x,y):
            queue = deque()
            queue.append((x,y))
            while queue:
                x, y = queue.popleft()
                for i in range(8):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    if 0 <= nx < l and 0 <= ny < l:
                        if graph[nx][ny] == 0:
                            graph[nx][ny] = graph[x][y] + 1
                            queue.append((nx,ny))
                        if graph[nx][ny] == -1:
                            graph[nx][ny] = graph[x][y] + 1
                            return graph[r][c]
    if r==i and c==j:
        print(0)
    else:
        answer = bfs(i,j)
        print(answer)