[백준 - Python] 7562. 나이트의 이동 (DFS/BFS)

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

7562번: 나이트의 이동

 

코드

from collections import deque

t = int(input())

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

def bfs(mat):
    q = deque()
    q.append((x, y))
    mat[x][y] = 1
    while q:
        a, b = q.popleft()
        if a == xx and b == yy:
            return mat[xx][yy] - 1
        for i in range(8):
            nx = a + dx[i]
            ny = b + dy[i]
            if 0 <= nx < I and 0 <= ny < I:
                if mat[nx][ny] == 0:
                    q.append((nx, ny))
                    mat[nx][ny] = mat[a][b] + 1


for _ in range(t):
    I = int(input())
    mat = [[0 for _ in range(I)] for _ in range(I)]
    x, y = map(int, input().split())
    xx, yy = map(int, input().split())
    result = bfs(mat)
    print(result)

 

문제를 읽고 상하좌우, 대각선 방향으로 이동해 가는 문제와 유사하다고 생각하고

문제를 풀기 시작했다.

 

해당 문제는 최소 거리를 구하는 것이 핵심인 문제였고,

다시 말하면, 목표 지점까지 도달할 수 있는 길이 하나가 아니라 여러 개가 있을 수 있는 문제였다.

 

DFS는 방문한 정점의 모든 방위를 탐색하면서

목표지점까지의 모든 경우의 수를 모두 구해야 최소 거리를 알 수 있는 반면에,

 

BFS는 같은 이동거리에 있는 정점들을 모두 조사한 후에

한 정점이 목표 지점에 도달하면 그 즉시 탐색을 종료할 수 있고, 해당 거리가 최소거리가 된다.

 

따라서, 최소 거리 혹은 최단 거리라는 명시가 있으면 DFS보다는 BFS를 사용해야 한다!

 

방문한 곳은 1로 방문처리를 해주고, mat 2차원 배열을 이동 거리를 저장하는 변수로 활용했다.

초기 값이 1로 설정되고 이후로 1씩 더해지기 때문에

목표 지점에 도달한 이후에는 해당 지점의 값에서 -1 해준 값을 반환해야 최소 이동 횟수를 구할 수 있다.

 

 

참고 자료

https://velog.io/@highcho/Algorithm-baekjoon-7562