문제
풀이
난이도가 있는 문제인 만큼 바로 풀어내진 못했다. 현재 이동 방향을 기준으로 원소를 계속 삽입해야한다는 아이디어는 생각했으나 어떻게 코드를 짜야하는 지에 대한 감이 부족했다 🥲
문제 내용은 다른 보통의 bfs 문제와 비슷하게,
출발점과 도착점이 존재하고 주어진 map 내에서 길을 따라 도착점으로 이동하는 최소시간을 구하는 문제이다.
따라서 bfs()를 통해 현재 위치를 기준으로 벽을 피해 상하좌우로 이동해주면 되는데 여기서 추가적으로 붙은 조건은 바로 매 초 마다 이동할 방향에 대하여 최소 1개, 최대 K개의 빈 칸을 이동할 수 있다는 것이다.
즉, 다시 말하면 현재 방향에 대하여 1칸에서 k칸까지 이동하는 과정은 모두 동일하게 1초의 시간이 걸리기 때문에 그 다음 방향으로 넘어가는 것보다 우선순위가 더 높다는 뜻이다. 결론적으로 1칸에서부터 k칸까지 이동한 위치를 차례로 먼저 큐에 삽입한다. 이 과정을 코드로 표현하면 아래와 같다.
for dx, dy in d:
X, Y = x + dx, y + dy
nk = 1
while (
nk <= K
and 0 <= nx < N
and 0 <= ny < M
and graph[X][Y] != "#"
and check[X][Y] > check[x][y] # point
):
if check[X][Y] == INF:
q.append((X, Y))
check[X][Y] = check[x][y] + 1
X += dx
Y += dy
nk += 1현재 방향으로 한 칸씩 어떻게 이동할 수 있을 지 꽤 고민을 했었는데 그냥 현재 dx, dy 값을 계속 더해주면 되는 것이었다 (!) 참고로 칸 수는 k까지 이동 가능하므로 nk 변수를 통해 반복문이 돌 때마다 1씩 더해주며 확인해주면 된다.
위 코드를 통해 하나 더 짚어야 할 부분이 있는데, 바로 방문했던 위치의 경우 무조건 방문하지 않게 하면 안된다는 것이다. 탐색 순서의 방향에 따라 처음 방문한 위치의 값이 최소값이 아닐 수도 있기 때문이다. 왜 그러한 지는 이 포스팅을 보면 이해하기 쉽다.
따라서 방문할 위치의 값이 현재값보다 크다면 방문한 길을 건너 뛰고 다음 길을 또 탐색하게 해야하며 해당 부분에 대한 코드는 #point 부분이다.
아래는 전체 코드이다. (참고로 좌표값을 확인해야하는 것이므로 check 리스트도 x, y축을 모두 확인하기 위해 2차원 배열로 만들었다.)
from collections import deque
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
N, M, K = map(int, input().split()) # N:세로 M:가로, K: step
D = [list(input()) for _ in range(N)]
sx, sy, ex, ey = map(int, input().split())
# 인덱스와 위치값을 맞춰주기 위해 모두 1씩 빼준다
sx -= 1
sy -= 1
ex -= 1
ey -= 1
check = [[float("inf")] * M for _ in range(N)]
q = deque()
q.append((sx, sy))
check[sx][sy] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
nk = 1
while (
nk <= K
and 0 <= nx < N
and 0 <= ny < M
and D[nx][ny] != "#"
and check[nx][ny] > check[x][y]
):
if check[nx][ny] == float("inf"):
q.append((nx, ny))
check[nx][ny] = check[x][y] + 1
nx += dx[i]
ny += dy[i]
nk += 1
if check[ex][ey] == float("inf"):
print(-1)
else:
print(check[ex][ey])
