[백준][Python] 7562 나이트의 이동

그래프, bfs / 실버 1

♟️

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

7562번: 나이트의 이동

 

 

내 풀이

from collections import deque

def bfs(x, y, ex, ey):
    q = deque()
    q.append((x, y))

    while q:
        cx, cy = q.popleft()

        if cx == ex and cy == ey:
            return chess[cx][cy]

        for i in range(8):
            nx, ny = cx + dx[i], cy + dy[i]

            if 0 <= nx < l and 0 <= ny < l and chess[nx][ny] == 0:
                chess[nx][ny] += chess[cx][cy] + 1
                q.append((nx, ny))


T = int(input())

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

for _ in range(T):
    l = int(input())
    chess = [[0] * l for _ in range(l)]

    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())

    print(bfs(sx, sy, ex, ey)) # 현재 좌표, 목적지 좌표

 

 

코드 설명

 

그림을 참고해, 나이트가 한 번에 이동할 수 있는 칸을 저장한다.

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

 

테스트 케이스의 수 T만큼 반복한다.

l X l 크기의 이차원 리스트를 0으로 초기화한다.

나이트가 현재 있는 칸(sx, sy)과 이동하려고 하는 칸(ex, ey)을 입력받아 저장한다.

bfs를 호출할 때 이 좌표들을 넘겨준다.

for _ in range(T):
    l = int(input())
    chess = [[0] * l for _ in range(l)]

    sx, sy = map(int, input().split())
    ex, ey = map(int, input().split())

    print(bfs(sx, sy, ex, ey)) # 현재 좌표, 목적지 좌표

 

 

✔️ bfs 함수

 

종료 조건: 현재 좌표 = 목적지 좌표

현재 값을 리턴한다.

if cx == ex and cy == ey:
    return chess[cx][cy]

 

한 번에 이동할 수 있는 좌표 8개를 검사한다.

 

새 좌표가 범위 내에 있으면서, 아직 방문하지 않은 칸이라면(chess[nx][ny] == 0)

새 좌표의 값을 기존 좌표의 값 + 1로 변경한 후, deque에 추가하고, 계속해서 값을 갱신한다.

for i in range(8):
    nx, ny = cx + dx[i], cy + dy[i]

    if 0 <= nx < l and 0 <= ny < l and chess[nx][ny] == 0:
        chess[nx][ny] += chess[cx][cy] + 1
        q.append((nx, ny))