🐢 장군

1. 문제 링크

16509번: 장군

2. 코드

Python3 34136KB 68ms

"""
[16509] 장군

💛 문제
오랜만에 휴가를 나온 호근이는 문득 동아리방에 있는 장기가 하고 싶어졌다. 
하지만 장기를 오랫동안 하지 않은 탓인지 예전에는 잘 쓰던 상을 제대로 쓰는 것이 너무 힘들었다. 
호근이를 위해 상을 어떻게 써야 할지 도와주자.

위 그림은 10×9 크기의 장기판을 나타내며, 
상은 (5, 4)에, 왕은 (1, 4)에 자리 잡고 있는 기물이다. 
(0, 3)과 (2, 5)를 꼭짓점으로 하는 사각형과, (7, 3)과 (9, 5)를 꼭짓점으로 하는 사각형은 왕이 위치할 수 있는 궁성이라고 한다.
상은 위 그림과 같이 8가지 방법으로 움직일 수 있는데, 상, 하, 좌, 우로 한 칸을 이동한 후에 같은 방향 쪽 대각선으로 두 칸 이동한다.

만약 상이 이동하는 경로에 위 그림과 같이 다른 기물이 있다면 상은 그쪽으로 이동할 수 없다. 
또한, 상이 장기판을 벗어날 수도 없다.

10×9 크기의 장기판 위에 상과 왕의 처음 위치가 주어졌을 때, 
상이 왕에게 도달할 수 있는 최소 이동 횟수를 구하여라.

💚 입력
첫 번째 줄에는 상의 위치를 의미하는 정수 R1, C1이 주어진다.
두 번째 줄에는 왕의 위치를 의미하는 정수 R2, C2가 주어진다. 

장기판에서 Ri (0 ≤ Ri ≤ 9)는 행을, Ci (0 ≤ Ci ≤ 8)는 열을 의미한다.
왕은 항상 궁성에 자리 잡고 있으며, 상과 왕의 위치는 겹치지 않는다.

💙 출력
상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력한다. 만약 도달할 수 없다면 -1을 출력한다.
"""

from collections import deque

# 상의 위치
r1, c1 = map(int, input().split())

# 왕의 위치
r2, c2 = map(int, input().split())

step_x = [
        #### [상하좌우 중 한칸 이동, 대각선으로 한칸 이동]
        # 위
		[-1, -2],
        [-1, -2],
        # 왼쪽
        [0, -1],
        [0, 1],
        # 아래쪽
        [1, 2],
        [1, 2],
        # 오른쪽
        [0, -1],
        [0, 1]
	]
step_y = [
        # 위
		[0, -1],
        [0, 1],
        # 왼쪽
        [-1, -2],
        [-1, -2],
        # 아래쪽
        [0, -1],
        [0, 1],
        # 오른쪽
        [1, 2],
        [1, 2]
	]

visit = [[0] * 9 for _ in range(10)]
# 위, 왼쪽, 아래쪽, 오른쪽
dx = [-3, -3, -2, 2, 3, 3, -2, 2]
dy = [-2, 2, -3, -3, -2, 2, 3, 3]

def in_range(nx, ny) :
    return 0 <= nx < 10 and 0 <= ny < 9

# 이동 경로 살펴보기
def move(x, y, i) :
    for j in range(2) :
        # [상하좌우 중 한칸 이동, 대각선으로 한칸 이동]
        nx = x + step_x[i][j]
        ny = y + step_y[i][j]
        
        # 이동 경로에 왕이 있으면
        if (nx == r2 and ny == c2) :        
            return 0
    return 1


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

# 상의 상하좌우 한칸 + 대각선 두칸 후 위치
def bfs(x, y) :
    queue = deque()
    queue.append([x, y, 0])
    visited[x][y] = 1

    while queue :
        x, y, cnt = queue.popleft()

        for i in range(8) :
            nx = x + dx[i]
            ny = y + dy[i]

            # 상하좌우 중 한칸 + 대각선 두칸 했을 때 범위 넘어가면! for 문으로 돌아간다
            if not in_range(nx, ny) :
                continue
        
            # 그 전에 이동경로 살펴보기.. 왕 있다면! for 문으로 돌아간다
            # 기존 상의 위치 + 이동한 방향 인덱스
            if not move(x, y, i) :
                continue

            # 이미 방문 했다면
            if visited[nx][ny] == 1 :
                continue
            
            # 왕 만난다면
            if nx == r2 and ny == c2 :
                # 상이 왕에게 도달할 수 있는 최소 이동 횟수를 출력
                return cnt + 1

            visited[nx][ny] = 1
            # cnt += 1 하고 밑에 cnt를 대입했는데 숫자가 더 커져서 나옴 뭘까?
            queue.append([nx, ny, cnt + 1])

    # 만약 도달할 수 없다면 -1을 출력
    return -1

# 상의 위치
print(bfs(r1, c1))

3. 해설

8방향마다, 한칸 이동 + 대각선 두번 이동 하는 방향 배열을 만들어 주었다.

• 먼저 방향을 지정해서 한칸이동 + 대각선 두번 했을 때 범위 넘어가면 pass
• 그전에 이동 과정에서 2가지 경우에 왕이 있다면 pass
• 이미 방문 했다면 pass
• 마지막으로 왕 만났다면 최소 이동 횟수를 증가시킨다
• 그렇지 않다면 방문처리 하고 현재 위치를 queue 에 append 하고 빌 때까지 while 문 돌린다