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

문제 풀이 1

• 큐에 현재 좌표와 이동횟수 0을 삽입
• 탐색이 진행될 때 마다 이동횟수를 1씩 더해서 큐에 삽입
• 목표 좌표에 도달 했다면, 이동횟수를 출력하고 while문 빠져나오기

코드

from collections import deque
dy = [-1, -2, -2, -1, 1, 2, 2, 1]
dx = [-2, -1, 1, 2, 2, 1, -1, -2]
n = int(input())
graph = []
for _ in range(n):
    l = int(input())
    visited = [[0] * l for _ in range(l)]
    y, x = map(int,input().split())
    target_y, target_x = map(int,input().split())
    queue = deque()
    queue.append((y, x, 0))
    visited[y][x] = 1
    while queue:
        y, x, d = queue.popleft()
        if y == target_y and x == target_x:
            print(d)
            break
        for i in range(8):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < l and 0 <= nx < l and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                queue.append((ny, nx, d + 1))

문제 풀이 2

• 큐에 현재 좌표를 삽입
• 탐색을 진행하면서, 좌표가 범위를 벗어나지 않고, 그래프의 값이 0인 경우 (아직 탐색 X) 
• 그래프 이전 값 + 1 한 값을 현재 그래프 좌표에 업데이트
• 목표 좌표에 도달하면 값을 출력

코드

import sys
from collections import deque
# 나이트가 이동할 수 잇는 방향
dy = [-2, -1, 1, 2, 2, 1, -1, -2]
dx = [1, 2, 2, 1, -1, -2, -2, -1]
# 테스트 케이스 갯수
num = int(sys.stdin.readline())

for n in range(num):
    m = int(sys.stdin.readline())   # 체스판 한 변의 길이
    y, x = map(int,sys.stdin.readline().split())    # 현재좌표
    target_y, target_x = map(int,sys.stdin.readline().split())  # 도달해야하는 좌표
    graph = [[0] * m for _ in range(m)] # 가로세로 m크기의 체스판 모양 그래프 만들기

    queue = deque()
    queue.append((y, x))
    while queue:
        yy, xx = queue.popleft()
        # 목표 좌표에 도달하면 그 좌표 값 출력
        if yy == target_y  and xx == target_x :
            print(graph[target_y][target_x])
            break
        # 이동할 수 있는 모든 방향을 보면서
        # 처음 방문하는 곳이면 
        # 이전 좌표값에 1을 더한 값을 현재좌표에 넣고
        # 현재좌표 삽입
        for i in range(8):
            new_y = yy + dy[i]
            new_x = xx + dx[i]
            if 0 <= new_y < m and 0 <= new_x < m and graph[new_y][new_x] == 0:
                graph[new_y][new_x] = graph[yy][xx] + 1
                queue.append((new_y, new_x))