[JAVA] BOJ 백준 16930번 - 달리기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16930번: 달리기

---

2. 내가 푼 방법

시간 초과가 관건인 BFS 문제이다.

 

이동할 수 있는 체육관의 위치를 큐에 담을 때 중복을 제거하는 것이 중요하다. 같은 방향으로 1 ~ K 만큼을 이동할 수 있다는 것은, 달리는 중간에 방향을 꺾을 수 없다는 의미이다. 따라서 벽에 부딪히거나 범위를 벗어나면 break; 문을 통해 K번의 for문을 빠져나온다.

 

또한, 이전에 도착한 적 없는 위치일 경우에는 체육관 위치를 큐에 추가하고, 만약 이전에 도착한 적 있는 위치일 경우에는 시간에 따라 분기한다. 이전에 방문했던 시간보다 더 늦게 방문하게 된다면 break;를 통해 빠져나오고, 이전에 방문했던 시간과 동일한 시간에 방문하게 된다면 더 먼 곳까지 이동할 수 있기 때문에 continue;문을 통해 달리기를 지속한다.

public static void solution() {
    // BFS

    Queue<int[]> queue = new ArrayDeque<>();

    visit[sx][sy] = 1;
    queue.add(new int[]{sx, sy, 1});

    while (!queue.isEmpty()) {
        int[] q = queue.poll();
        int move = q[2];

        for (int d = 0; d < dx.length; d++) {
            for (int k = 1; k <= K; k++) {
                int nx = q[0] + dx[d] * k;
                int ny = q[1] + dy[d] * k;

                if (nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == '#') break;

                if (nx == ex && ny == ey) {
                    result = move;
                    return;
                }

                if (visit[nx][ny] == 0) {
                    visit[nx][ny] = move + 1;
                    queue.add(new int[]{nx, ny, move + 1});
                }
                else if (visit[nx][ny] == move + 1) continue;
                else break;
            }
        }
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16930.java

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

class Main {
    static int N, M, K;
    static char[][] arr;
    static int[][] visit;
    static int sx, sy;
    static int ex, ey;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    static int result;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        // BFS

        Queue<int[]> queue = new ArrayDeque<>();

        visit[sx][sy] = 1;
        queue.add(new int[]{sx, sy, 1});

        while (!queue.isEmpty()) {
            int[] q = queue.poll();
            int move = q[2];

            for (int d = 0; d < dx.length; d++) {
                for (int k = 1; k <= K; k++) {
                    int nx = q[0] + dx[d] * k;
                    int ny = q[1] + dy[d] * k;

                    if (nx < 0 || ny < 0 || nx >= N || ny >= M || arr[nx][ny] == '#') break;

                    if (nx == ex && ny == ey) {
                        result = move;
                        return;
                    }

                    if (visit[nx][ny] == 0) {
                        visit[nx][ny] = move + 1;
                        queue.add(new int[]{nx, ny, move + 1});
                    }
                    else if (visit[nx][ny] == move + 1) continue;
                    else break;
                }
            }
        }
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(result+"");

        bw.flush();
        bw.close();
    }

    public static void input() 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());
        arr = new char[N][M];
        visit = new int[N][M];
        result = -1;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        st = new StringTokenizer(br.readLine());
        sx = Integer.parseInt(st.nextToken()) - 1;
        sy = Integer.parseInt(st.nextToken()) - 1;
        ex = Integer.parseInt(st.nextToken()) - 1;
        ey = Integer.parseInt(st.nextToken()) - 1;

        br.close();
    }
}

---

4. 결과 및 회고

같은 시간에 방문했을 때 더 먼 곳까지 달릴 수 있으므로 continue;를 해줘야 했던 부분에서 살짝 트릭이 가미된 문제라고 생각한다. 시간 초과를 해결하기 위해 어떻게 코드를 개선해야 할지 고민하는 과정이 재밌었다.ㅎㅎ