boj.kr/7562 나이트의 이동 (silver1) 파이썬 풀이

1. 체스판에서 나이트가 움직일 수 있는 8개 좌표 저장

2. bfs 방식으로 출발 좌표에서 도착 좌표로 가는 횟수 계산

풀이1) 그래프를 방문체크 배열로 사용하면서 카운트하거나 풀이2) deque에서 카운트

 

#풀이1 - 그래프(방문체크 배열)에 움직인 횟수를 저장

from collections import deque
dx = (1, 1, -1, -1, 2, 2, -2, -2)
dy = (2, -2, 2, -2, 1, -1, 1, -1)
def bfs(x1, y1, x2, y2, I):
    if (x1, y1) == (x2, y2):
        return 0
    dq = deque()
    dq.append((x1, y1))
    board = [[0]*I for _ in range(I)]
    board[x1][y1] = 1
    while dq:
        (x, y) = dq.popleft()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < I and 0 <= ny < I and not board[nx][ny]:
                if nx == x2 and ny == y2:
                    return board[x][y]
                else:
                    board[nx][ny] = board[x][y] + 1
                    dq.append((nx, ny))
                    
N = int(input())
for _ in range(N):
    I = int(input())
    (x1, y1) = map(int, input().split())
    (x2, y2) = map(int, input().split())
    print(bfs(x1, y1, x2, y2, I))

 

#풀이2 - dq에 append하는 값 중 하나로 움직인 횟수를 전달

dy = (-2, -2, -1, -1, 1, 1, 2, 2)
dx = (-1, 1, -2, 2, -2, 2, -1, 1)
from collections import deque
def bfs(sx, sy, ex, ey, N):
    dq = deque()
    dq.append((sy, sx, 0))
    while dq:
        (cy, cx, d) = dq.popleft()
        if cy == ey and cx == ex:
            return d
        for i in range(8):
            ny = cy + dy[i]
            nx = cx + dx[i]
            if 0<=ny<N and 0<=nx<N and graph[ny][nx] == 0:
                graph[ny][nx] += 1
                dq.append((ny, nx, d+1))

T = int(input())
for _ in range(T):
    N = int(input())
    graph = [[0]*N for _ in range(N)]
    (sx, sy) = map(int, input().split())
    (ex, ey) = map(int, input().split())
    print(bfs(sx, sy, ex, ey, N))

 

bfs 응용 문제에서 모든 탐색 좌표를 저장해두는 것이 중요하다.

이 문제의 경우는 방문체크용 변수 없이 그래프 상에 방문체크 및 카운트 할 수 있다.