[BOJ]1600. 말이 되고픈 원숭이

문제

https://www.acmicpc.net/problem/1600

 

사용 알고리즘

BFS

 

풀이

고려사항

1. 말로 이동하는 경우인지 원숭이로 이동하는 경우인지

2. 말로 이동하는 경우 횟수 관리

 

후기

1. 이 문제의 keypoint는 K(말로 이동한 횟수)를 관리하는 것이다.

처음 풀이에는 K를 횟수 카운트 관리만 진행하며,  visited를 2차원 배열로 진행했는데 오답이였다.

이는 주어진 보드판에 장애물이 존재하기 때문이다.

예를 들어 가는 길 중간에 왼쪽 위 노란색에서 오른쪽 아래의 노란 칸으로 이동하는 경우

원숭이로 이동하다가 장애물 존재 시, 말로 이동할 수 있는 경우가 남아있어 이동이 가능한 경우가 있는데

말의 이동 횟수를 다 사용하여 말로 이동할 수 없는 경우 장애물을 만났을 때

이미 못간다고 방문기록을 남겨놓으면 오류가 발생하기 때문이다.

때문에 visited 배열을 K까지 3차원 배열로 관리하도록 변경하였다.

2. 위의 K만 관리한다면 이후는 다른 BFS와 크게 다르지 않다.

(이동 가능 범위 확인, 장애물 여부 확인, 방문 여부 확인)

이때, 나는 visited는 방문 여부만 확인하고 ccnt로 현재 횟수를 queue에 함께 넣어 관리했는데

visited에 넣어 관리하는 방법도 깔끔한 방법으로 생각된다.

visited로 cnt를 관리하려면

visited[ni][nj][k+1] = visited[i][j][k] + 1 형식으로 변경하여 풀이하게 된다.

 

코드

import sys
from collections import deque

input = sys.stdin.readline

didj = [(1, 0), (0, 1), (-1, 0), (0, -1)]
horse = [(-1, -2), (-2, -1), (-2, 1), (-1, 2), (1, -2), (2, -1), (1, 2), (2, 1)]


def bfs():
    visited = [[[0] * (K + 1) for _ in range(M)] for _ in range(N)]
    visited[0][0][K] = 1
    q = deque([(0, 0, 0, K)])

    while q:

        ccnt, ci, cj, ck = q.popleft()

        if ci == N - 1 and cj == M - 1:
            return ccnt

    	# 원숭이로 이동하는 경우
        for di, dj in didj:
            ni, nj = ci + di, cj + dj
            if (0 <= ni < N and 0 <= nj < M
                and arr[ni][nj] == 0 and visited[ni][nj][ck] == 0):
                q.append((ccnt + 1, ni, nj, ck))
                visited[ni][nj][ck] = 1

    	# 말로 이동하는 경우
        if ck > 0:
            for di, dj in horse:
                ni, nj = ci + di, cj + dj
                if (0 <= ni < N and 0 <= nj < M
                    and arr[ni][nj] == 0 and visited[ni][nj][ck - 1] == 0):
                    q.append((ccnt + 1, ni, nj, ck - 1))
                    visited[ni][nj][ck - 1] = 1

    return -1


K = int(input())
M, N = map(int, input().split())

arr = [list(map(int, input().split())) for _ in range(N)]
print(bfs())

 

결과