[Java][백준][플레티넘 3] 달리기 - 16930

1. 문제 정보

• 문제명: 달리기
• 문제 번호: 16930
• 플랫폼: 백준
• 문제 링크: https://www.acmicpc.net/problem/16930
• 알고리즘 유형: BFS
• 한 줄 핵심: 한 번에 최대 K칸까지 직선 이동 가능한 최단거리 탐색 문제

 

 

2. 문제 요약

격자에서 시작점에서 도착점까지 이동할 때, 매 턴마다 상하좌우 한 방향으로 1칸 이상 K칸 이하 이동할 수 있다.
단, 벽(#)은 통과할 수 없고 격자 밖으로 나갈 수 없다.

따라서 일반적인 1칸 BFS와 다르게, 한 방향으로 1~K칸을 모두 확인해야 한다는 점이 핵심이다.

 

3. 내 풀이 아이디어

기본은 BFS이고, 현재 칸에서 4방향 각각에 대해 1~K칸을 직선으로 확장했다.

중요 포인트는 아래 3가지다.

• 벽을 만나면 해당 방향 탐색 즉시 중단
• 범위를 벗어나면 해당 방향 탐색 중단
• 이미 더 짧은 거리로 방문한 칸을 만나면 그 이후는 볼 필요 없으므로 중단
  (dist[nx][ny] < dist[x][y] + 1)

이 조건이 없으면 시간 초과가 나기 쉬운 문제다.

 

 

4. 풀이 방법

1. dist 배열을 초기화한다.

• 벽은 Integer.MAX_VALUE
• 빈 칸은 -1 (미방문)

2. 시작점 거리를 0으로 두고 큐에 넣는다.
3. BFS에서 현재 좌표를 꺼낸다.
4. 4방향 각각에 대해 j=1..K까지 전진하며 다음을 검사한다.

• 범위 밖이면 break
• 벽이면 break
• 이미 더 짧은 거리 방문 칸이면 break
• 처음 방문 칸이면 dist = 현재거리 + 1로 갱신 후 큐에 삽입

5. 탐색 종료 후 도착점 dist 출력 (-1이면 도달 불가)

 

5. 코드

import java.io.*;
import java.util.*;

public class Main {

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0 ,0};

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());

        char[][] map = new char[n][m];

        for (int i = 0; i < n; i++)  map[i] = br.readLine().toCharArray();

        st = new StringTokenizer(br.readLine());
        int x1 = Integer.parseInt(st.nextToken()) - 1;
        int y1 = Integer.parseInt(st.nextToken()) - 1;
        int x2 = Integer.parseInt(st.nextToken()) - 1;
        int y2 = Integer.parseInt(st.nextToken()) - 1;

        int[][] dist = new int[n][m];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == '#') {
                    dist[i][j] = Integer.MAX_VALUE;
                } else {
                    dist[i][j] = -1;
                }
            }
        }

        dist[x1][y1] = 0;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x1, y1});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            for (int i = 0; i < 4; i++) {
                for (int j = 1; j <= k; j++) {
                    int nx = x + j * dx[i];
                    int ny = y + j * dy[i];

                    if (nx < 0 || ny < 0 || nx >= n || ny >= m) break;
                    if (map[nx][ny] == '#') break;
                    if (dist[nx][ny] != -1 && dist[nx][ny] < dist[x][y] + 1) break;

                    if (dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[x][y] + 1;
                        queue.add(new int[]{nx, ny});
                    }
                }
            }
        }

        System.out.println(dist[x2][y2]);
    }
}

 

 

6. 코드 해설

• dist[nx][ny] != -1 && dist[nx][ny] < dist[x][y] + 1 조건:
  • 이미 더 좋은 경로가 확보된 칸을 만나면 더 멀리 갈 필요가 없어서 break
• if(map[nx][ny] == '#') break:
  • 벽을 통과할 수 없으므로 해당 방향 전진 종료
• dist == -1일 때만 큐 삽입:
  • 같은 레벨 중복 방문을 줄여 탐색량을 제어

이 문제는 “이동 자체”보다 중단 조건 설계가 더 중요하다

 

 

7. 회고

일반 BFS처럼 1칸씩만 보면 안 되고, 한 번에 K칸까지 뻗는 구조라 구현 난이도가 높았다.
특히 어디서 break 해야 하는지를 정확히 잡는 게 핵심이었다.
더 짧은 거리 방문 칸을 만났을 때 break 조건을 이해하고 나서 원할하게 풀 수 있었다.

 

 

8. 태그

백준, BOJ, Java, 16930, 달리기, BFS, 그래프탐색, 격자탐색, 최단거리, 구현