🐹 장군

1. 문제 링크

16509번: 장군

2. 코드

Python3 34104KB 88ms

# 상 위치
sx, sy = map(int, input().split())
# 왕 위치
kx, ky = list(map(int, input().split()))

# 상좌, 상우, 하좌, 하우, 좌상, 좌하, 우상, 우하
dx = [[-1, -1, -1], [-1, -1, -1], [1, 1, 1], [1, 1, 1], [0, -1, -1], [0, 1, 1], [0, -1, -1], [0, 1, 1]]
dy = [[0, -1, -1], [0, 1, 1], [0, -1, -1], [0, 1, 1], [-1, -1, -1], [-1, -1, -1], [1, 1, 1], [1, 1, 1]]

dist = [[0] * 9 for _ in range(10)]

from collections import deque

def bfs():
    q = deque([])
    q.append((sx, sy))
    while q:
        x, y = q.popleft()
        # 왕에 도달
        if x == kx and y == ky:
            return dist[x][y]
        for i in range(8):
            flag = True
            nx, ny = x, y
            for j in range(3):
                nx += dx[i][j]
                ny += dy[i][j]
                # 장기판 밖으로 이동할 때
                if nx < 0 or nx >= 10 or ny < 0 or ny >= 9:
                    flag = False
                    break
                # 이동 경로에 다른 기물(왕)이 있을 시
                if j != 2 and nx == kx and ny == ky:
                    flag = False
                    break
            # 이동 가능한 칸이고 아직 방문하지 않았다면
            if flag == True and dist[nx][ny] == 0:
                dist[nx][ny] = dist[x][y] + 1   # 최단 거리 표시 
                q.append((nx, ny))
        
    # 왕에게 도달 불가 시
    return -1

print(bfs())

3. 해설

최단 경로를 구하기 위해 bfs(너비우선탐색)을 사용해주었다.

각 위치의 최단 경로 정보를 dist 2차원 배열에 넣어준다.

상이 움직일 수 있는 총 8가지의 경우에서 이동 가능 위치 3가지를 2중 포문으로 확인해준다.

각 위치가 장기판 내에 있고, 이동 경로에 다른 기물(왕)이 없는지 확인해주고 조건을 만족했을 때 이동한 칸의 위치가 처음 도착한 위치라면(dist의 값이 0) 해당 위치의 최단 거리 값을 넣어준다.

최단 거리는 ‘이동 바로 직전 칸 거리 + 1’이다.

현재 상의 위치가 왕의 위치가 같다면 해당 위치의 dist값을 리턴한다.

만약 큐를 모두 돌았을 때도 왕을 만나지 못한다면 -1을 리턴한다.