[BOJ] 말이 되고픈 원숭이 in Python

박준규·2022년 5월 27일
0

알고리즘

목록 보기
37/39

문제 풀러 가기!

이 문제 처음 읽고 일반환된 코드를 생각하지 못해 틀렸습니다.

중요한 것은 문제에서 이야기한 말 이동의 횟수에 따라 이동할 수 있는 것이 달라진다는 것. 그리고 이걸 방문 배열에서 어떻게 체크할 것인가? 입니다. 만약에 자꾸 틀리신다면, 아래 TEST CASE를 분석해보시면, 느낌이 오실겁니다.. 일반적인 2차원 방문 배열로는 이 문제를 풀 수 없구나..

1
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 0

즉, 낚시 문제였던 것 같습니다. 다행이 k값을 고려하여 방문 배열을 3차원으로 늘려줬더니 풀리게되었습니다. 물론 Python은 6600ms, PyPy는 600ms로 통과되었는데, Python은 참.. 정말 느린 언어네요.. 조금씩 Kotlin과 C++로 언어를 옮겨야할 것 같습니다..

문제풀이

일단 문제의 조건을 준수합시다.

원숭이는 말처럼 이동 할수도 있고 그냥 상 하 좌 우 격자 이동만 할 수 있습니다. 그리고 말처럼 이동하는 것은 제약 사항이 있습니다. 바로 k번만 이동할 수 있다는 것이죠. 따라서 이 모두를 고려 해야 합니다.

그러면 어떤 이동이 우선이 되어야 할까요?

제 생각이지만 상 하 좌 우 격자 이동이 우선시 되어야 할 것 같습니다. 그 이유는 위에서 제시된 Test Case에서는 상 하 좌 우로만 이동하다가 마지막에 말 점프를 합니다. 말 점프를 먼저하게 되면, 방금 말씀드린 경로를 찾을 수 없게 됩니다. 따라서 격자 이동을 먼저 하고 말 이동을 하는 것이 모든 경로를 고려할 수 있다고 생각했습니다.

그러면 방문 배열

1 차원: 말이동을 몇번 했는지
2 차원: 행
3 차원: 열

로 구성하여 BFS 탐색을 시도한다면 도착 지점까지의 가장 빠른 경로를 탐색할 수 있습니다.

따라서 전체 코드는 아래와 같이 구성됩니다.

전체 코드
from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
w, h = map(int, input().split())

INF = int(1e9)

arr = [list(map(int, input().split())) for _ in range(h)]
visited = [[[INF for _ in range(w)] for _ in range(h)] for _ in range(k+1)]
delta = [(0, 1), (1, 0), (0, -1), (-1, 0)]
horse_delta = [
    (-1, -2),
    (-2, -1),
    (-1, 2),
    (-2, 1),
    (1, 2),
    (2, 1),
    (2, -1),
    (1, -2)
]

sx, sy = 0, 0
ex, ey = h-1, w-1
def bfs(sx, sy):

    q = deque([(sx, sy, 0, 0)])

    while q:
        x, y, cnt, c = q.popleft()

        if x == ex and y == ey:
            return cnt

        for i in range(4):
            nx, ny = x + delta[i][0], y + delta[i][1]

            if not (0 <= nx < h and 0 <= ny < w): continue
            if arr[nx][ny] == 1: continue
            if visited[c][nx][ny] != INF : continue

            visited[c][nx][ny] = cnt + 1
            q.append((nx, ny, cnt + 1, c))
        
        if c >= k: continue

        for i in range(8):
            nx, ny = x + horse_delta[i][0], y + horse_delta[i][1]

            if not (0 <= nx < h and 0 <= ny < w): continue
            if arr[nx][ny] == 1: continue
            if visited[c+1][nx][ny] != INF: continue

            visited[c+1][nx][ny] = cnt + 1
            q.append((nx, ny, cnt + 1, c + 1))
    
    return -1

print(bfs(sx, sy))

질문과 오타 수정 언제나 환영입니다.

profile
'개발'은 '예술'이고 '서비스'는 '작품'이다

0개의 댓글