[BOJ][🟡5][백준#16509] 장군

문제 출처

BAEKJOON Online Judge #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을 출력한다.

예제

예제 1

입력

4 2
2 5

출력

1

예제 2

입력

0 1
8 4

출력

3

예제 3

입력

0 2
1 4

출력

5

My Sol

from collections import deque

def main():
    I, J = 10, 9
    bi, bj = map(int, input().split())
    ti, tj = map(int, input().split())
    D = {
        (-1,0): [(-1,-1),(-1,1)],
        (1,0): [(1,1),(1,-1)],
        (0,1): [(-1,1),(1,1)],
        (0,-1): [(-1,-1),(1,-1)]
    }

    Q = deque([(bi, bj)])
    visit = [[0]*J for _ in range(I)]
    visit[bi][bj] = 1

    while Q:
        ni, nj = Q.popleft()
        for i1, j1 in D.keys():
            si1, sj1 = ni+i1, nj+j1
            if not (0<=si1<I and 0<=sj1<J): continue
            if si1==ti and sj1==tj: continue
            for i2, j2 in D[(i1, j1)]:
                si2, sj2 = si1+i2, sj1+j2
                if si2==ti and sj2==tj: continue
                si3, sj3 = si2+i2, sj2+j2
                if not (0<=si3<I and 0<=sj3<J): continue
                if visit[si3][sj3]: continue
                if si3==ti and sj3==tj: return visit[ni][nj]
                visit[si3][sj3] = visit[ni][nj]+1
                Q.append((si3, sj3))

    return -1

print(main())

간단하게 생각하면 간단하지만, 경로 선택에 있어 장애물을 통과하지 못한다는 점을 간과하면 쉽게 함정에 빠질 수 있는 문제였다. 알고리즘은 BFS를 사용한다.

1. 가로, 세로는 0부터 9, 0부터 8이므로 각각 I, J를 10, 9로 두어 넘지 못하게 하였다.
2. 시작점과 목표점의 좌표를 받아 저장한다.
3. 첫번째 스텝을 key로 하고, 해당 step을 밟고 이동할 수 있는 2개의 방향을 리스트로 저장한 것을 value로 두는 딕셔너리 D를 지정한다.
4. 시작점 좌표를 deque Q에 추가한다. 반복문은 Q에 저장될 모든 좌표를 꺼내 사용하였음에도 왕에 닿지 못할 때까지 진행한다.
5. D의 key들은 말 그래도 현재 좌표에서 첫 발을 밟는 4개의 방향이다. 첫 발을 밟는 좌표를 si1, sj1으로 두었다. 이 첫 발이 범위를 벗어나면 continue한다. 또한 이는 이동의 과정이므로 왕이 해당 위치에 있어도 목표가 아닌 장애물로 작용하기 때문에 si1과 sj1에 왕이 있어도 continue한다.
6. 다음은 첫 발의 위치를 key로 하는 value들의 이동 방향을 각각 i2, j2로 하여 반복문을 진행한다. 첫 발을 밟은 위치 si1, sj1에 i2와 j2를 각각 더해 대각선으로 한 칸 이동한다. 여기에서는 해당 방향으로 2번 이동하므로 중간 과정에 왕이 있으면 continue한다.
7. i2와 j2를 si2와 sj2에 더해 si3와 sj3을 만든다. 이것이 ni와 nj의 좌표에서 이동할 수 있는 8개의 이동 좌표이다. 만약 이 좌표가 범위를 벗어나면 continue한다.
8. 방문 여부를 따지면서 해당 좌표에 도달하기 위한 최소 이동 수를 저장하는 visit 2차원 배열을 활용한다. visit은 모든 좌표를 0으로 초기화하고 시작점에서 1로 두었다. 이후에 이동 위치가 가능하다면 직전 위치의 최소 이동수인 visit[ni][nj]에 1을 더한 것을 visit[si3][sj3]에 저장하게 된다. 때문에 visit[si3][sj3]에 값이 있으면 이미 방문했던 점이므로 continue한다.
9. si3와 sj3이 ti와 tj라면 왕에 닿은 것이므로 visit[ni][nj]를 반환한다. 왜냐하면 처음에 시작점에서 visit[bi][bj]를 1로 두었기 때문에 visit[ni][nj]+1이 아니라 1을 뺀 visit[ni][nj]를 반환하는 것이다.
10. 만약 이동 좌표가 범위 내이면서 왕이 아니라면 visit[si3][sj3]에 visit[ni][nj]+1을 저장하며 방문을 체크하고, Q에 (si3, sj3)을 추가하여 다음 이동의 시작점으로 삼는다.

결과

맞았습니다!!