[Algorithm🧬] 정올 1106 : 장기

문제

import sys
from collections import deque

def BFS(N, M, R, C, S, K):

    # 이동 가능한 방향 8가지 (x, y 그래프로 보는거랑 행렬로 생각했을 때랑 축의 위치도 반대고 x, y 쌍 위치도 반대임!)
    move = [(-2, 1), (-1, 2), (1, 2), (2, 1), (2, -1), (1, -2), (-1, -2), (-2, -1)]

    q = deque()

    q.append((R, C, 0))
    board[R][C] = 1

    while q:
        r, c, cnt = q.popleft()

        if r == S and c == K:
            return cnt

        for x, y in move:
            tr, tc, tcnt = r + x, c + y, cnt + 1

            if not 1 <= tr <= N:
                continue
            if not 1 <= tc <= M:
                continue

            # 같은 것도 포함.
            if (tcnt >= board[tr][tc]):
                continue

            q.append((tr, tc, tcnt))
            board[tr][tc] = tcnt

    return -1

# BFS 8 방향으로 이동 가능.
# 행 R N
# 열 M C

N, M = map(int, sys.stdin.readline().split())
R, C, S, K = map(int, sys.stdin.readline().split())
# board = [[10000000] * (M + 2)] * (N + 2)
board = [[0] + [100000] * M + [0] if 1 <= i <= N else [0] * (M + 2) for i in range(N + 2)]

BFS(N, M, R, C, S, K)

print(board[S][K])

처음에는 tcnt > board[tr][tc] 로 같은 것을 포함 안했더니 답이 다르게 나와서 고침.
그랬더니 주어진 test case 에 대한 답이 제대로 나와서 기대했으나

39 43
9 27 4 36

6

이 5로 나오는 문제가 있었는데, 처음 입력에서 100000 (큰 수) 로 padding 부분까지 채워버려서 그런 것이었다. board = [[0] + [100000] * M + [0] if 1 <= i <= N else [0] * (M + 2) for i in range(N + 2)] 으로 장기가 갈 수 없는 부분에는 0 을 넣어서 혹시라도 접근했을 때 더이상 바뀌지 않도록 바꿔주었다.

2트

padding 없이 풀었는데 계속 에러나서 뭐지 했는데 처음에 행이랑 열 반대로 입력받음.. 이런 어이 없는 실수에 주의하자....