문제
동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다.
| x |
| x |
|
x |
|
|
| x |
|
| 말 |
|
|
x |
|
|
| x |
| x |
| x |
|
근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다.
이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨 왼쪽 위에서 시작해서 맨 오른쪽 아래까지 가야한다. 인접한 네 방향으로 한 번 움직이는 것, 말의 움직임으로 한 번 움직이는 것, 모두 한 번의 동작으로 친다. 격자판이 주어졌을 때, 원숭이가 최소한의 동작으로 시작지점에서 도착지점까지 갈 수 있는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다. W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.
출력
첫째 줄에 원숭이의 동작수의 최솟값을 출력한다. 시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.
예제 입력 1
1
4 4
0 0 0 0
1 0 0 0
0 0 1 0
0 1 0 0
예제 출력 1
4
예제 입력 2
2
5 2
0 0 1 1 0
0 0 1 1 0
예제 출력 2
-1
출처
알고리즘 분류
[백준 1600] 말이 되고픈 원숭이 — “점프 횟수”까지 상태로 들고 가는 BFS
원숭이는 원래 상/하/좌/우로만 움직이는데, 딱 K번까지는 말(나이트)처럼 점프할 수 있다. 문제는 (0,0)에서 (H-1, W-1)까지 최소 이동 횟수를 구하는 것.
이 문제를 풀면서 제일 중요한 포인트는 이거였다.
같은 칸에 도착해도 “점프를 몇 번 썼는지”에 따라 이후 선택지가 완전히 달라진다.
그래서 방문 처리를 2차원이 아니라 3차원으로 해야 한다.
1) 문제 풀이 아이디어
왜 BFS인가?
한 번 움직일 때마다 비용이 1(걸어가든 점프든 1회)이니까, 최단거리는 BFS가 딱 맞다.
왜 visited가 3차원인가?
보통 격자 최단거리는 visited[x][y]면 끝난다.
근데 이 문제는 점프를 최대 K번 쓸 수 있어서 상태가 하나 더 붙는다.
(x, y, jump)= (x, y)에 점프를 jump번 사용한 상태로 도착
즉, 같은 (x,y)라도
점프를 0번 쓴 상태
점프를 3번 쓴 상태
는 서로 다른 상태다.
그래서 코드에서도 이렇게 만들었다.
visited = [[[0 for _ in range(K+1)] for _ in range(W)] for _ in range(H)]
visited[x][y][jump]는 “그 상태로 도착했을 때 이동 횟수”를 저장한다.
2) 시간 복잡도 계산
상태 개수를 먼저 세면 쉽다.
좌표 경우의 수:
H * W점프 사용 횟수 상태:
K + 1(0 ~ K)
즉 전체 상태 수는 H * W * (K+1).
각 상태에서 이동은
걸음 4방향 + 말 8방향 = 총 12방향 검사
그래서 시간 복잡도는:
O(H * W * (K+1) * 12) ≈ O(H * W * K)
공간 복잡도는 visited 때문에:
O(H * W * (K+1))
3) 로직 순서에 따른 “부분 코드” 해설
이제 내 코드 흐름대로, BFS가 어떻게 굴러가는지 순서대로 뜯어보자.
(1) 입력 & 맵/방문 배열 준비
K = int(sys.stdin.readline().strip())
W, H = map(int,sys.stdin.readline().split())
maps = [list(map(int,sys.stdin.readline().split())) for _ in range(H)]
visited = [[[0 for _ in range(K+1)] for _ in range(W)] for _ in range(H)]
maps[x][y] == 1이면 장애물이라 이동 불가visited[x][y][jump] == 0이면 그 상태는 아직 안 가본 상태 (거리 저장도 같이 겸함)
(2) 방향 배열 12개 만들기 (걸음 4 + 점프 8)
dx = [-1,1,0,0, -1,-2, -2,-1, 1,2, 2,1]
dy = [0,0,-1,1, -2,-1, 1,2, -2,-1, 1,2]
내 코드에서는 for i in range(12)로 돌면서
i < 4면 상하좌우i >= 4면 말 점프
로 분기한다.
(3) BFS 시작 상태 넣기
queue = deque()
queue.append([coor_x, coor_y, jump])
시작 상태는 (0,0,0)
즉, 시작점에서 점프를 한 번도 안 쓴 상태로 출발.
(4) 큐에서 꺼내고, 도착 체크
x, y, jump = queue.popleft()
if x == H-1 and y == W - 1:
return max(visited[x][y])
여기서 내 코드는 목적지에 도착하면 max(visited[x][y])를 반환한다.
왜 max냐면 목적지 (H-1, W-1)도
점프 0번으로 도착
점프 1번으로 도착
…
점프 K번으로 도착
여러 상태로 들어올 수 있고, 내 visited는 “0은 미방문”이라서 값이 있는 것들 중 실제 거리(이동 횟수)가 기록된다.
그중 가장 의미 있는 값을 뽑겠다는 방식이다.
(5) 4방향(걸음) 처리 파트
if i < 4:
if jump == 0 :
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny][0] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump])
visited[nx][ny][0] = visited[x][y][0] + 1
else:
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny][jump] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump])
visited[nx][ny][jump] = visited[x][y][jump] + 1
이 파트는 결론적으로 “걸어서 이동하면 점프 사용 횟수는 그대로”라는 의미다.
지금
jump == 0이면visited[...,0]채널만 쓰면 되고jump > 0이면 해당jump채널로 계속 이동한다
즉, 걸음 이동은 상태가 (nx,ny,jump) 그대로 유지된다.
(6) 8방향(말 점프) 처리 파트
else:
if jump < K:
if jump == 0:
if 0 <= nx < H and 0 <= ny <W and visited[nx][ny][jump+1] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump+1])
visited[nx][ny][jump + 1] = visited[x][y][0] + 1
else:
if 0 <= nx < H and 0 <= ny <W and visited[nx][ny][jump + 1] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump+1])
visited[nx][ny][jump+1] = visited[x][y][jump] + 1
말 이동은 “점프를 1번 사용한다”가 핵심이다.
점프를 더 쓸 수 있는지
jump < K확인가능하면 다음 상태는
(nx, ny, jump+1)
그리고 거리 기록도 +1 해준다.
내 코드가 jump == 0일 때 따로 분기를 둔 이유는,
처음 점프하는 순간엔 visited[x][y][0] 채널에서 거리를 가져와서 jump+1 채널로 옮겨야 하기 때문(이라고 생각하고 작성한 흐름)이다.
(7) 끝까지 못 가면 -1
return -1
BFS가 다 끝났는데도 도착 못 하면 답이 없다.
4) 전체 코드
import sys
from collections import deque
K = int(sys.stdin.readline().strip())
# H = x, W = y
W, H = map(int,sys.stdin.readline().split())
maps = [list(map(int,sys.stdin.readline().split())) for _ in range(H)]
visited = [[[0 for _ in range(K+1)] for _ in range(W)] for _ in range(H)]
def bfs(coor_x, coor_y) -> int:
global maps
global visited
jump = 0
dx = [-1,1,0,0, -1,-2, -2,-1, 1,2, 2,1]
dy = [0,0,-1,1, -2,-1, 1,2, -2,-1, 1,2]
queue = deque()
queue.append([coor_x, coor_y, jump])
while queue:
x, y, jump = queue.popleft()
if x == H-1 and y == W - 1:
return max(visited[x][y])
for i in range(12):
nx = x + dx[i]
ny = y + dy[i]
# 상하좌우 케이스
if i < 4:
# 걸어서 방문한 케이스
if jump == 0 :
# 범위 내, 걸어서 미방문, 장애물 X
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny][0] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump])
visited[nx][ny][0] = visited[x][y][0] + 1
# 경로상 한번이라도 점프를 해서 온 케이스
else:
# 범위 내, 걸어서가지만 점프를 해서 온 케이스이므로 점프 미방문, 장애물 X
if 0 <= nx < H and 0 <= ny < W and visited[nx][ny][jump] == 0 and maps[nx][ny] != 1:
# 점프는 안하니 jump 는 그대로 넣는다.
queue.append([nx,ny,jump])
visited[nx][ny][jump] = visited[x][y][jump] + 1
# 말의 움직임 케이스(점프를 할 경우)
else:
# 점프를 아직 할 수 있는 상태인지 체크
if jump < K:
# 현재까지 점프를 한번도 안한경우.
if jump == 0:
if 0 <= nx < H and 0 <= ny <W and visited[nx][ny][jump+1] == 0 and maps[nx][ny] != 1:
# 이제 점프를 할거니까 jump +1
queue.append([nx,ny,jump+1])
# 이제 점프를 할거니까, 걸어왔던 걸음 수를 베껴와서 점프 기록에 옮겨준다.
visited[nx][ny][jump + 1] = visited[x][y][0] + 1
# 현재까지 점프를 한번이라도 한 경우.
else:
if 0 <= nx < H and 0 <= ny <W and visited[nx][ny][jump + 1] == 0 and maps[nx][ny] != 1:
queue.append([nx,ny,jump+1])
visited[nx][ny][jump+1] = visited[x][y][jump] + 1
return -1
print(bfs(0,0))