[BOJ/BFS+DFS] 백준 16930 - 달리기 (Java)

16930 - 달리기

https://www.acmicpc.net/problem/16930

문제

다이어트를 위해 NxM 크기의 체육관을 달림
체육관은 1x1 크기의 칸으로 나뉘어져 있고, 칸은 빈 칸 or 벽/ (x, y): x행 y열에 있는 칸 
매 초마다 위, 아래, 오른쪽, 왼쪽 중에서 이동할 방향 하나 고르고, 그 방향으로 최소 1개, 최대 K개의 빈칸 이동

=> 시작점 (x1, y1), 도착점(x2, y2) 주어졌을 때, 시작점에서 도착점으로 이동하는 최소 시간?

입력
첫째 줄: 체육관의 크기 N과 M, 1초에 이동할 수 있는 칸의 최대 개수 K
둘째 줄 ~ N개의 줄: 체육관의 상태/ 빈 칸: '.', 벽: '#'
마지막 줄: 네 정수 x1, y1, x2, y2 -> 두 칸은 서로 다른 칸이고 항상 빈 칸
출력
(x1, y1)에서 (x2, y2)로 이동하는 최소 시간?
이동할 수 없는 경우 -1 출력

---

풀이

• `int[][] dist = new int[N][M]`: 각 좌표까지의 최소 이동 횟수
• `Integer.parseInt(st.nextToken()) - 1`: 입력값 1-based 좌표((1, 1)부터 시작) -> 0-based index

 

• 범위 초과 or 벽 만남 or 더 빠른 거리로 도달 -> 중단

if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
if (map[nx][ny] == '#') break;
if (dist[nx][ny] != -1 && dist[nx][ny] <= dist[cur[0]][cur[1]]) break;

• 아직 방문 X -> 거리 저장 + 큐에 추가

if (dist[nx][ny] == -1) {
    dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
    queue.offer(new int[]{nx, ny});
}

---

코드

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

// 달리기
public class boj_16930 {
    static int N, M, K;
    static char[][] map;
    static int[][] dist;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        dist[x][y] = 0;
        queue.offer(new int[]{x, y});

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();

            for (int dir = 0; dir < 4; dir++) {
                for (int k = 1; k <= K; k++) {
                    int nx = cur[0] + dx[dir] * k;
                    int ny = cur[1] + dy[dir] * k;

                    if (nx < 0 || ny < 0 || nx >= N || ny >= M) break;
                    if (map[nx][ny] == '#') break;
                    if (dist[nx][ny] != -1 && dist[nx][ny] <= dist[cur[0]][cur[1]]) break;

                    if (dist[nx][ny] == -1) {
                        dist[nx][ny] = dist[cur[0]][cur[1]] + 1;
                        queue.offer(new int[]{nx, ny});
                    }
                }
            }
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        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;

        dist = new int[N][M];
        for (int[] row : dist) Arrays.fill(row, -1);

        bfs(x1, y1);
        System.out.println(dist[x2][y2]);
    }
}