[백준] 1600 말이 되고픈 원숭이 - 골드 3
[오늘의 문제]
https://www.acmicpc.net/problem/1600
[오늘의 학습 키워드]
- 너비 우선 탐색
- 구현
- 그래프 탐색, 그래프 이론
- 격자 그래프
1. 문제설명
동물원을 탈출한 원숭이가 0, 0 좌표에 존재합니다.
이 원숭이가 N, M 좌표로 이동하려고 하는데 말이 되고 싶어 말처럼 이동이 가능합니다.
말처럼 이동하는데는 최대 K번 이동이 가능하고 그 이후에는 인접한 4방향으로 이동이 가능합니다.
격자판에 정보가 주어질 때, 원숭이가 최소한의 동작으로 0, 0 좌표에서 N, M 좌표로 이동하는 방법을 구하는 문제 입니다.
[제한사항]
- 시간 제한 2초
- 메모리 제한 256MB
- N과 M은 1이상 200이하의 자연수
- K는 0이상 30이하의 정수
- 격자판에 주어진 정보 0은 평지, 1은 장애물
2. 접근방식
이 문제를 해결하기 위해서 우선 주어진 정보들을 정리해 보겠습니다.
1. 0은 이동가능 1은 이동 불가능
2. 말처럼 이동하는 경우 벽을 넘어서 이동이 가능하다.
3. 말처럼 이동이 종료된 경우 인접한 4방향으로만 이동이 가능하다.
4. N, M 위치로 이동이 불가능한 경우 -1을 출력한다.
주어진 조건들을 이용해 문제를 해결해야 하는데 한가지 주의할 점이 있습니다.
말처럼 이동하는 경우 최대 K번 이동이 가능한데 말처럼 이동을 한 경우와 그렇지 않은 경우를 구분해서 출력해 주어야 합니다.
무슨 소리냐면
0 0 0 0 0
1 1 1 1 0
1 1 1 1 0
1 1 1 1 0
이렇게 격자판 정보가 주어진다면 말처럼 이동하는 경우와 인접한 좌표로 이동하는 경우를 구분해서 이동해 주어야 한다는 소리입니다.
위 격자판에서 말처럼 이동 후 인접 방향으로 이동한다면 0, 0 에서는 말처럼 이동이 불가능 하기 때문에 인접방향으로 이동해 주어야 하고
이동이 완료되면 N, M 위치에 도착했을 때 이동 정보는 7이 출력 되겠죠
이를 방지하기 위해서 3차원 visited 배열을 사용해 주어야 합니다.
말처럼 이동이 최대 K번 가능하다 하였으니 visited 배열을 K + 1개 생성하여 말처럼 이동한 경우를 저장하고
그렇지 않은 경우를 구분해서 저장해 주어야 오류없이 출력이 가능하겠죠
그 외에는 일반적인 BFS 처럼 동작을 실시해주면 될 것입니다.
3. 코드
import sys
input = sys.stdin.readline
from collections import deque
# 말의 이동
hx = [-1, -2, -2, -1, 1, 2, 2, 1]
hy = [-2, -1, 1, 2, 2, 1, -1, -2]
# 인접방향 이동
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def BFS():
while queue:
x, y, k = queue.popleft()
# 종료조건
if x == N - 1 and y == M - 1:
return visited[x][y][k]
# 인접 4방향 이동
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < N and 0 <= ny < M:
# 말의 이동을 실시하지 않았으니 K는 변화없이 저장
if MAPS[nx][ny] == 0 and visited[nx][ny][k] == -1:
visited[nx][ny][k] = visited[x][y][k] + 1
queue.append((nx, ny, k))
# 말의 이동
if k < K:
for h in range(8):
nnx = x + hx[h]
nny = y + hy[h]
if 0 <= nnx < N and 0 <= nny < M:
# 말처럼 이동 했으니 이동 횟수를 소모해 K + 1에 저장
if MAPS[nnx][nny] == 0 and visited[nnx][nny][k + 1] == -1:
visited[nnx][nny][k + 1] = visited[x][y][k] + 1
queue.append((nnx, nny, k + 1))
# 도달할 수 없는 경우
return -1
# 입력
K = int(input())
M, N = map(int, input().split())
MAPS = [list(map(int, input().split())) for _ in range(N)]
visited = [[[-1] * (K + 1) for _ in range(M)] for _ in range(N)]
# visited 초기화
visited[0][0][0] = 0
queue = deque([(0, 0, 0)]) # 시작좌표 , K번 이동 가능한 횟수
print(BFS())[코드설명]
# 입력
K = int(input())
M, N = map(int, input().split())
MAPS = [list(map(int, input().split())) for _ in range(N)]
visited = [[[-1] * (K + 1) for _ in range(M)] for _ in range(N)]
# visited 초기화
visited[0][0][0] = 0
queue = deque([(0, 0, 0)]) # 시작좌표 , K번 이동 가능한 횟수
print(BFS())
우선 입력을 받고 3차원 visited 배열을 생성해 주었습니다.
3차원 visited 배열은 N x M 크기의 방문 배열이 K개 존재하는 것이죠
그 다음 queue에 시작 좌표정보 0, 0 과 K번 이동 횟수 0을 저장해 BFS 탐색을 시작해 줍니다.
# 말의 이동
hx = [-1, -2, -2, -1, 1, 2, 2, 1]
hy = [-2, -1, 1, 2, 2, 1, -1, -2]
# 인접방향 이동
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def BFS():
while queue:
x, y, k = queue.popleft()
# 종료조건
if x == N - 1 and y == M - 1:
return visited[x][y][k]
# 인접 4방향 이동
for d in range(4):
nx = x + dx[d]
ny = y + dy[d]
if 0 <= nx < N and 0 <= ny < M:
# 말의 이동을 실시하지 않았으니 K는 변화없이 저장
if MAPS[nx][ny] == 0 and visited[nx][ny][k] == -1:
visited[nx][ny][k] = visited[x][y][k] + 1
queue.append((nx, ny, k))
# 말의 이동
if k < K:
for h in range(8):
nnx = x + hx[h]
nny = y + hy[h]
if 0 <= nnx < N and 0 <= nny < M:
# 말처럼 이동 했으니 이동 횟수를 소모해 K + 1에 저장
if MAPS[nnx][nny] == 0 and visited[nnx][nny][k + 1] == -1:
visited[nnx][nny][k + 1] = visited[x][y][k] + 1
queue.append((nnx, nny, k + 1))
# 도달할 수 없는 경우
return -1
BFS 탐색을 시작할 때 인접방향 이동 dx, dy 와 말의 이동 hx, hy를 설정해 주었습니다.
BFS 탐색을 시작할 때 x, y, k 를 입력받아 시작하는데 우선 종료 조건을 설정해 주었습니다.
종료 조건은 BFS 탐색 중 가장 먼저 N, M 좌표에 도착하는 경우 그때의 visited 배열을 출력해 주어야 하죠
종료 조건에 만족하지 않는 경우 인접한 4방향 이동과 말의 이동을 실시해 주어야 하죠
인접한 4방향 이동의 경우 말의 이동 횟수를 소모하지 않기 때문에 다음 이동 위치로 이동한 경우 nx, ny, k를 그대로 저장해 주고
visited 배열은 그대로 k에 저장해 주어야 하죠
말의 이동을 실시한 경우 말의 이동 횟수 K를 소모한 것이기 때문에 말의 이동 가능 조건을 구분해 주기 위해 if를 이용해 k < K
조건을 통해 말의 이동이 가능한 경우를 구해주고 이동을 실시한다면 k + 1 번째 visited 배열에 저장해 주어야 하죠
visited 배열에 저장할 때는 기존의 이동 정보를 갱신해 주어야 하기 때문에 이전 정보 + 1 을 현재 정보에 저장해 주어야 합니다.
모든 이동을 완료했는데 N, M 좌표에 도달하지 못했다면 -1을 반환해 주어야 합니다.
4. 결과
[회고]
처음 제가 풀었던 코드는 다음과 같습니다.
import sys
input = sys.stdin.readline
from collections import deque
K = int(input())
M, N = map(int, input().split())
MAPS = [list(map(int, input().split())) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
horse_queue = deque([(0, 0)])
queue = deque()
visited[0][0] = 0
# 말의 이동
hx = [-1, -2, -2, -1, 1, 2, 2, 1]
hy = [-2, -1, 1, 2, 2, 1, -1, -2]
# 인접방향 이동
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
while horse_queue:
x, y = horse_queue.popleft()
# 1. 말의 이동을 통해 갈 수 있는 모든 곳 표시
while K:
for k in range(8):
nx = x + hx[k]
ny = y + hy[k]
if 0 <= nx < N and 0 <= ny < M:
if MAPS[nx][ny] != 1 and visited[nx][ny] == -1:
horse_queue.append((nx, ny))
queue.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
K -= 1
while queue:
x, y = queue.popleft()
# 2. 인접방향 이동
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
if MAPS[nx][ny] != 1 and visited[nx][ny] == -1:
queue.append((nx, ny))
visited[nx][ny] = visited[x][y] + 1
print(visited[N-1][M-1])
이동 정보를 구분해 queue 와 horse_queue를 저장하고 말의 이동이 완료된 경우 인접방향 이동을 실시해 주었습니다.
모든 이동을 완료하고 visited 배열을 출력하였는데 3%에서 틀리더라구요
반례를 찾던 중 아까 접근방식에서 설명한 반례가 존재하였습니다.
반례를 해결하기 위해서는 DP를 이용하거나 BFS를 다르게 이용해 주어야 하는데 3차원 visited 배열을 통해 문제를
해결할 수 있었습니다.
문제를 풀면서 3차원 배열을 생각하니 문제 구조가 벽 부수고 이동하기 문제랑 비슷하더라구요 벽을 부수는 경우와
벽을 부수지 않는 경우를 구분해 BFS 탐색을 실시하여 문제를 해결해야 했었죠
이 문제도 동일하게 말이 이동하는 경우와 그렇지 않은 경우를 구분해 문제를 해결했어야 하죠
다음번에도 비슷한 문제를 해결하며 학습을 이어 나가겠습니다.