[JAVA] BOJ 백준 6087번 - 레이저 통신

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

이 문제의 핵심은 위치와 방향 상태를 이전에 방문한 적 있는지 확인하기 위해 Integer형인 visit 배열을 사용한다는 것이다.

 

처음 이 문제를 풀었을 때는 boolean 자료형으로 이전 방문을 체크했는데, boolean을 사용할 경우에는 올바른 답이 나오지 않는다. 그 이유는 우리가 카운팅 해야 할 값은 필요한 거울의 수이며, 해당 위치와 방향까지 도달하기까지 거울을 사용할 수도 있고 없는, 즉 일정하지 않는 필요한 거울의 수가 큐에 쌓인다.

 

따라서 먼저 나오는 위치와 방향이 항상 제일 작은 거울의 수를 보장하지 않기 때문에, Integer 자료형으로 확인한 visit 배열과 Math.min을 이용해야 한다.

Queue<int[]> queue = new LinkedList<>(); // x, y, 방향, 거울카운팅
Integer[][][] visit = new Integer[N][M][4];
int[] dx = {-1, 0, 1, 0};
int[] dy = {0, -1, 0, 1};

for (int d = 0; d < dx.length; d++) {
    queue.add(new int[]{sx, sy, d, 0});
    visit[sx][sy][d] = 0;
}

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

    if (arr[x][y] == 'C' && !(x == sx && y == sy)) {
        result = Math.min(result, visit[x][y][d]);
        continue;
    }

    for (int i = 0; i < dx.length; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        int ncnt = (i != d) ? cnt + 1 : cnt;

        if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
        if (arr[nx][ny] == '*') continue;
        if (visit[nx][ny][i] != null && visit[nx][ny][i] <= ncnt) continue;

        visit[nx][ny][i] = ncnt;
        queue.add(new int[]{nx, ny, i, ncnt});
    }
}

---

3. 자바 코드

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

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

class Main {
    static int N, M;
    static char[][] arr;
    static int sx, sy;
    static int result;

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

    public static void solution() {
        Queue<int[]> queue = new LinkedList<>(); // x, y, 방향, 거울카운팅
        Integer[][][] visit = new Integer[N][M][4];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, -1, 0, 1};

        for (int d = 0; d < dx.length; d++) {
            queue.add(new int[]{sx, sy, d, 0});
            visit[sx][sy][d] = 0;
        }

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

            if (arr[x][y] == 'C' && !(x == sx && y == sy)) {
                result = Math.min(result, visit[x][y][d]);
                continue;
            }

            for (int i = 0; i < dx.length; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                int ncnt = (i != d) ? cnt + 1 : cnt;

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (arr[nx][ny] == '*') continue;
                if (visit[nx][ny][i] != null && visit[nx][ny][i] <= ncnt) continue;

                visit[nx][ny][i] = ncnt;
                queue.add(new int[]{nx, ny, i, ncnt});
            }
        }
    }

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

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

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

                if (arr[i][j] == 'C') {
                    sx = i;
                    sy = j;
                }
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

오늘따라 집중을 잘 못하고,, 잔실수를 하는 것 같다.. 정신차렷...