[백준] 16930번 달리기

달리기

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	8830	1303	839	13.213%

문제

진영이는 다이어트를 위해 N×M 크기의 체육관을 달리려고 한다. 체육관은 1×1 크기의 칸으로 나누어져 있고, 칸은 빈 칸 또는 벽이다. x행 y열에 있는 칸은 (x, y)로 나타낸다.

매 초마다 진영이는 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향을 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈 칸을 이동한다.

시작점 (x1, y1)과 도착점 (x2, y2)가 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간을 구해보자.

입력

첫째 줄에 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K가 주어진다.

둘째 줄부터 N개의 줄에는 체육관의 상태가 주어진다. 체육관의 각 칸은 빈 칸 또는 벽이고, 빈 칸은 '.', 벽은 '#'으로 주어진다.

마지막 줄에는 네 정수 x1, y1, x2, y2가 주어진다. 두 칸은 서로 다른 칸이고, 항상 빈 칸이다.

출력

(x1, y1)에서 (x2, y2)로 이동하는 최소 시간을 출력한다. 이동할 수 없는 경우에는 -1을 출력한다.

제한

• 2 ≤ N, M ≤ 1,000
• 1 ≤ K ≤ 1,000
• 1 ≤ x1, x2 ≤ N
• 1 ≤ y1, y2 ≤ M

예제 입력 1

3 4 4
....
###.
....
1 1 3 1

예제 출력 1

3

예제 입력 2

3 4 1
....
###.
....
1 1 3 1

예제 출력 2

8

예제 입력 3

2 2 1
.#
#.
1 1 2 2

예제 출력 3

-1

내 코드

시간 초과

from collections import deque

DIRECTIONS = [(0, -1), (0, 1), (-1, 0), (1, 0)]  # 상하좌우 방향

def get_minimum_time(N, M, K, gym, x1, y1, x2, y2):
    queue = deque([(x1, y1)])
    gym[y1][x1] = 0  # 첫 위치 방문처리

    while queue:
        x, y = queue.popleft()

        for dx, dy in DIRECTIONS:

            # 1부터 K까지 확인
            for k in range(1, K + 1):
                nx, ny = x + (dx * k), y + (dy * k)

                # 이동 범위인지 확인
                if 0 <= nx < M and 0 <= ny < N:

                    # 벽(#) 있으면 다음 방향
                    if gym[ny][nx] == '#':
                        break

                    # .이면 이동 시간 입력
                    if gym[ny][nx] == '.':
                        gym[ny][nx] = gym[y][x] + 1

                        # 도착 확인
                        if (nx, ny) == (x2, y2):
                            return gym[ny][nx]

                        # 도착 아니면 이동한 위치 큐에 추가
                        queue.append((nx, ny))

    return -1  # 큐가 비면 도달 불가이므로 -1 리턴

N, M, K = map(int, input().split())  # 세로, 가로, 최대이동칸수
gym = [list(input()) for _ in range(N)]
y1, x1, y2, x2 = map(int, input().split())

print(get_minimum_time(N, M, K, gym, x1 - 1, y1 - 1, x2 - 1, y2 - 1))

chatGPT

from collections import deque

def min_time_to_reach(N, M, K, gym, start, end):
    x1, y1 = start
    x2, y2 = end

    # 방향 벡터 (상, 하, 좌, 우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    # BFS 초기화
    queue = deque([(x1 - 1, y1 - 1)])  # (행, 열)
    visited = [[-1] * M for _ in range(N)]
    visited[x1 - 1][y1 - 1] = 0

    while queue:
        x, y = queue.popleft()
        time = visited[x][y]

        # 도착점에 도달하면 최소 시간 반환
        if (x, y) == (x2 - 1, y2 - 1):
            return time

        # 4방향으로 최대 K칸 이동 가능
        for dx, dy in directions:
            for step in range(1, K + 1):
                nx, ny = x + dx * step, y + dy * step

                # 범위 벗어나거나 벽 만나면 중단
                if not (0 <= nx < N and 0 <= ny < M) or gym[nx][ny] == '#':
                    break

                # 아직 방문하지 않았거나 더 빠른 시간에 도달할 경우 갱신
                if visited[nx][ny] == -1:
                    visited[nx][ny] = time + 1
                    queue.append((nx, ny))
                elif visited[nx][ny] <= time:
                    break  # 불필요한 탐색 방지

    return -1  # 도달 불가능

# 입력 처리
N, M, K = map(int, input().split())
gym = [list(input().strip()) for _ in range(N)]
x1, y1, x2, y2 = map(int, input().split())
print(min_time_to_reach(N, M, K, gym, (x1, y1), (x2, y2)))

1. 입력 처리:
   • 먼저 체육관의 크기(N, M), 한 번에 이동할 수 있는 최대 칸 수(K), 그리고 체육관 상태(gym)를 입력받습니다.
   • 시작점과 목표점의 좌표도 입력받습니다. 입력된 좌표는 1-indexed이므로, 이를 0-indexed로 변환하여 사용합니다.
2. 방향 설정:
   • 이동할 수 있는 4가지 방향(상, 하, 좌, 우)을 directions 배열로 설정합니다. 이 배열을 사용하여 각 칸에서 이동할 수 있는 방향을 계산합니다.
3. BFS 탐색 초기화:
   • BFS를 위한 큐(queue)를 준비합니다. 큐에는 현재 위치와 해당 위치에 도달한 시간을 저장합니다.
   • visited 배열은 각 칸에 도달한 최소 시간을 기록하는 배열입니다. 시작점은 0초에 방문했으므로 visited 배열에서 시작점의 값을 0으로 설정합니다.
4. BFS 탐색 진행:
   • 큐에서 하나씩 위치를 꺼내며 탐색을 진행합니다. 각 위치에서 4방향으로 최대 K칸까지 이동할 수 있습니다.
   • 이동할 수 있는 칸에 대해 범위 체크와 벽 여부를 확인하여, 이동할 수 있다면 그 칸을 큐에 넣고 방문 시간을 갱신합니다.
   • 만약 목표 지점에 도달하면, 해당 시간(이동 횟수)을 즉시 반환합니다.
5. 불가능한 경우 처리:
   • 큐에 더 이상 방문할 수 있는 위치가 없으면 목표 지점에 도달할 수 없다는 의미이므로, 1을 반환하여 도달 불가능함을 나타냅니다.

최종적으로:

• 이 코드는 BFS를 사용하여 가장 빠르게 목표 지점에 도달하는 경로를 구합니다.
• 이동을 최적화하기 위해, 한 번에 최대 K칸까지 이동을 허용하며, 벽과 범위 체크를 통해 유효한 경로만 탐색합니다.

부가 질문

내 생각

1. K 까지 step 이동, 시간을 저장하는 배열까지 생각했으나, 시간이 초과된 것을 만나면 break 하는 것을 생각하지 못했다.