BOJ 1600

코드를 복사 붙여넣기 할 때는 조건을 잘 수정하자…

-이상 조건 하나 잘못 넣어서 삽질하는 바람에 시간 초과 뜬 인간이..

Input

첫째 줄에 정수 K가 주어진다.

둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다.

그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있는 곳으로는 이동할 수 없다. 시작점과 도착점은 항상 평지이다.

W와 H는 1이상 200이하의 자연수이고, K는 0이상 30이하의 정수이다.

from collections import deque
import sys
input = sys.stdin.readline

k = int(input())
w, h = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(h)]

Output

첫째 줄에 원숭이의 동작수의 최솟값을 출력한다.

시작점에서 도착점까지 갈 수 없는 경우엔 -1을 출력한다.

while q:
	if y == h-1 and x == w-1: return visited[y][x][z]

return -1

BFS

한 경우에 트리를 파고 들어가는 형식이라 DFS라고 생각했는데, BFS로 풀어야 했다.

이유는

동일한 시작점과 도착점을 가지는 와중에
방향에 따라 경우를 파서 들어가야 하기 때문이고,
모든 값을 저장하는 것이 아니라 먼저 조건을 만나는 경우에 출력하고 끝내기 때문이다.

이 문제의 조건은 다음과 같다.

k 번만 말과 같이 이동 가능
이후에는 인접한 칸 (상하좌우) 이동 가능

과정은

시작점은 (0,0)으로 동일 & 도착점은 (w-1,h-1)으로 동일
가능한 모든 direction을 시도해봐야 함
하나의 경우가 끝나면 count append, visited 초기화

이래서 DFS를 시도했으나, BFS와 3차원 배열을 활용하고 킥 포인트로 최소값 == 가장 먼저 break point를 만나는 경우 를 체크하면 됐다.

그래서 위의 과정을 수정해보면,

시작점과 도착점이 동일한 상태에서 여러번의 경우의 수가 존재하므로 bfs를 이용한다!
3차원 배열을 생성하여 가능한 모든 좌표에 대하여 k의 경우의 수를 포함한다.
초기화 하는 것이 아닌, 최소값을 구하는 경우이므로 가장 먼저 break point를 만나는 경우를 출력하고 종료하면 됨.

먼저, 정해진 direction이 존재하니 이걸 배열에 저장해 놓고,

1
2
3

# [dy, dx]
horse = [[2, -1], [-2, 1], [-1, -2], [-1, 2], [2, -1], [2, 1], [1, -2], [1, 2]]
dir = [[-1, 0], [0, -1], [0, 1], [1, 0]]

bfs를 정의한다.

def bfs():
  q = deque()
  q.append((0,0,k))
  visited = [[[0]*31 for _ in range(w)] for _ in range(h)]

여기서! k가 0 이상 30 이하이므로 31번 만큼 visited 배열을 더해서 3차원 배열을 만든다. 즉, visited를 별도의 배열이 아니라 기존 board에 추가하는 것.

break point를 설정하고,

while q:
  y, x, z = q.popleft()

  # 가장 먼저 도착하는 경우가 최소 횟수
  if y == h-1 and x == w-1: return visited[y][x][z]

default direction을 수행한다.

# default direction 먼저 append 하고
for d in dir:
  dy, dx = d
  ny = y + dy
  nx = x + dx

  if 0 <= ny < h and 0 <= nx < w and board[ny][nx] != 1 and visited[ny][nx][z] == 0:
    visited[ny][nx][z] = visited[y][x][z] + 1
    q.append((ny, nx, z))

더하여, 말의 이동경로는 디폴트가 아니라 경우를 따져야 하므로 밑에 조건을 덧붙인다.

# k > 0 인 경우 따로 경우를 더한다.
if z > 0:
  for d in horse:
    dy, dx = d
    ny = y + dy
    nx = x + dx

    ### 복붙할 때는 조건을 완벽히 확인하자...
    if 0 <= ny < h and 0 <= nx < w and board[ny][nx] != 1 and visited[ny][nx][z-1] == 0:
      visited[ny][nx][z-1] = visited[y][x][z] + 1
      q.append((ny, nx, z-1))

큐에서 break point를 만나지 못한 상태로 break 되면, 경우의 수가 존재하지 않는 것이므로 조건에 따라 -1을 출력한다.

return -1