[백준] 7562번 - 나이트의 이동 (DFS, BFS) - 결과 포함

www.acmicpc.net/source/25783143

로그인

언뜻 보면 기존의 문제들과 달라 보이지만 결국 유사한 문제이다.

단순하게 이동하는 방법이 변화했다고 생각하면 쉽게 풀린다.

기존에는 주로 x나 y값에 1을 더하거나 빼는 방식으로 인접한 정점으로 이동했다.

 

나이트는 두 칸을 상, 하, 좌, 우로 이동한 후에 이동한 방향에 좌 혹은 우로 한 칸 움직이는 방식으로 이동한다.

기존에 미리 정해 놓았던 x와 y 값의 움직임을 나이트의 움직임대로 8가지로 저장해놓으면 된다.

 

한 정점에서 범위를 벗어나거나 이미 방문한 정점을 제외하고

나이트의 움직임 8가지에 대해 BFS를 수행하면서 목표 위치까지 이동하는 갯수를 센다.

 

[소스코드]

from collections import deque

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

def bfs(curX, curY, tarX, tarY):
    queue = deque()
    queue.append([curX, curY])

    while queue:
        x, y = queue.popleft()
        if x == tarX and y == tarY:
            print(visited[x][y])
            return 0
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or ny < 0 or nx >= l or ny >= l:
                continue
            if visited[nx][ny] == 0:
                queue.append([nx, ny])
                visited[nx][ny] = visited[x][y] + 1


n = int(input())

for _ in range(n):
    l = int(input())
    visited = [[0] * l for _ in range(l)]

    curX, curY = map(int, input().split())
    tarX, tarY = map(int, input().split())

    bfs(curX, curY, tarX, tarY)