[JAVA] BOJ 백준 1726번 - 로봇

목차

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

---

1. 문제

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

1726번: 로봇

---

2. 내가 푼 방법

평소 BFS 문제는 상하좌우로 움직였지만, 이 문제는 로봇의 시작 위치와 방향에서 한 칸, 두 칸, 세 칸 이동하는 경우(Go)와 방향을 변경하는 경우(Turn)로 움직여야 했다.

 

먼저 위치와 방향이 동일한 적이 있는지 확인하기 위해 visit 배열에 몇 번 이동했는지를 저장해 주었다. 따라서 특정 위치와 방향에 도달했을 때 이동한 칸 수가 같거나 더 크다면 continue; 문으로 가지치기를 해주었다.

 

이 문제를 풀 때, 주의할 점은 벽에 가로막힐 경우에는 한 칸, 두 칸, 세 칸으로 이동하다가 막힌다는 것이다. 따라서 Go를 위한 for문에서 이동하지 못하는 경우에는 break; 문을 통해 바로 빠져나와야 했다.

while (!queue.isEmpty()) {
    int[] q = queue.poll();
    int x = q[0];
    int y = q[1];
    int d = q[2];
    int cnt = q[3];

    if (x == ex && y == ey && d == ed) {
        result = Math.min(result, cnt);
        continue;
    }

    // Go
    for (int i = 1; i <= 3; i++) {
        int nx = x + dx[d] * i;
        int ny = y + dy[d] * i;

        if (!checkRange(nx, ny)) break;
        if (visit[nx][ny][d] != null && visit[nx][ny][d] <= cnt + 1) continue;

        visit[nx][ny][d] = cnt + 1;
        queue.add(new int[]{nx, ny, d, cnt + 1});
    }

    // Turn
    if (d == 0 || d == 1) {
        for (int i = 2; i <= 3; i++) {
            if (visit[x][y][i] != null && visit[x][y][i] <= cnt + 1) continue;
            visit[x][y][i] = cnt + 1;
            queue.add(new int[]{x, y, i, cnt + 1});
        }
    }
    else {
        for (int i = 0; i <= 1; i++) {
            if (visit[x][y][i] != null && visit[x][y][i] <= cnt + 1) continue;
            visit[x][y][i] = cnt + 1;
            queue.add(new int[]{x, y, i, cnt + 1});
        }
    }
}

---

3. 자바 코드

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

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

class Main {
    static int N, M;
    static int[][] arr;
    static int sx, sy, sd; // 0123동서남북
    static int ex, ey, ed;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int result;

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

    public static void solution() {
        Queue<int[]> queue = new ArrayDeque<>();
        Integer[][][] visit = new Integer[N][M][4];

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

        while (!queue.isEmpty()) {
            int[] q = queue.poll();
            int x = q[0];
            int y = q[1];
            int d = q[2];
            int cnt = q[3];

            if (x == ex && y == ey && d == ed) {
                result = Math.min(result, cnt);
                continue;
            }

            // Go
            for (int i = 1; i <= 3; i++) {
                int nx = x + dx[d] * i;
                int ny = y + dy[d] * i;

                if (!checkRange(nx, ny)) break;
                if (visit[nx][ny][d] != null && visit[nx][ny][d] <= cnt + 1) continue;

                visit[nx][ny][d] = cnt + 1;
                queue.add(new int[]{nx, ny, d, cnt + 1});
            }

            // Turn
            if (d == 0 || d == 1) {
                for (int i = 2; i <= 3; i++) {
                    if (visit[x][y][i] != null && visit[x][y][i] <= cnt + 1) continue;
                    visit[x][y][i] = cnt + 1;
                    queue.add(new int[]{x, y, i, cnt + 1});
                }
            }
            else {
                for (int i = 0; i <= 1; i++) {
                    if (visit[x][y][i] != null && visit[x][y][i] <= cnt + 1) continue;
                    visit[x][y][i] = cnt + 1;
                    queue.add(new int[]{x, y, i, cnt + 1});
                }
            }
        }
    }

    public static boolean checkRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= M || arr[x][y] == 1) return false;
        return true;
    }

    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());
        arr = new int[N][M];
        result = Integer.MAX_VALUE;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

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

        br.close();
    }
}

---

4. 결과 및 회고

문제 함정에 빠지지 않도록 해보자