[BOJ/Java] 6087. 레이저 통신

📌 [BOJ/Java] 6087. 레이저 통신

🔗 문제 링크: 백준 6087번 - 레이저 통신

---

📖 문제 해석

2차원 맵에서 두 개의 레이저 🔦가 주어진다.
레이저는 **.(빈 공간)**에서 이동할 수 있으며, ***(벽)**을 통과할 수 없다.
이동할 때는 상하좌우 방향으로만 가능하며,
거울 (/ 또는 \)을 설치하여 빛의 방향을 변경할 수 있다.

✅ 목표는 시작 레이저에서 도착 레이저까지 최소한의 거울을 설치하는 것이다.

---

🛠️ 풀이 과정

이 문제는 BFS + 다익스트라 알고리즘을 응용하여 해결할 수 있다.
즉, **우선순위 큐(최소 힙)**를 사용하여 거울 설치 횟수가 적은 경로부터 탐색하는 방식이다.

1️⃣ 입력 처리 및 초기화

• W x H 크기의 맵 정보를 입력받고, 레이저의 시작점(C1)과 도착점(C2)을 찾는다.
• 4방향(상, 하, 좌, 우)으로 탐색을 수행하며, 거울을 설치해야만 방향을 바꿀 수 있다.

2️⃣ 우선순위 큐(BFS + 다익스트라) 활용

• (거울 설치 개수, x 좌표, y 좌표, 진행 방향)을 저장하는 **우선순위 큐(최소 힙)**를 사용한다.
• 거울 설치 횟수가 적은 경우부터 탐색하여, 더 적은 거울 개수로 도착하는 경우를 찾는다.
• 방문한 위치는 방향별로 기록하여 중복 탐색을 방지한다.

3️⃣ 최소 거울 설치 개수 찾기

• 도착 지점(C2)에 도착했을 때의 거울 개수 중 최소값을 출력한다.

---

💻 코드 구현 (Java)

import java.util.*;

public class Main {
    static class Node implements Comparable<Node> {
        int x, y, dir, mirrors;

        public Node(int x, int y, int dir, int mirrors) {
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.mirrors = mirrors;
        }

        @Override
        public int compareTo(Node o) {
            return this.mirrors - o.mirrors; // 거울 개수 기준으로 우선순위 큐 정렬
        }
    }

    static int W, H;
    static char[][] map;
    static int[][][] visited;
    static int[] dx = { -1, 1, 0, 0 }; // 상, 하, 좌, 우
    static int[] dy = { 0, 0, -1, 1 };
    static List<int[]> lasers = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        W = sc.nextInt();
        H = sc.nextInt();
        map = new char[H][W];
        visited = new int[H][W][4]; // 방향별 방문 배열 (상하좌우)

        for (int i = 0; i < H; i++) {
            String line = sc.next();
            for (int j = 0; j < W; j++) {
                map[i][j] = line.charAt(j);
                if (map[i][j] == 'C') {
                    lasers.add(new int[] { i, j }); // 레이저 위치 저장
                }
            }
        }

        System.out.println(bfs());
    }

    public static int bfs() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        int sx = lasers.get(0)[0], sy = lasers.get(0)[1];
        int ex = lasers.get(1)[0], ey = lasers.get(1)[1];

        for (int i = 0; i < 4; i++) {
            visited[sx][sy][i] = 0;
            pq.offer(new Node(sx, sy, i, 0)); // 모든 방향에서 시작 가능
        }

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (cur.x == ex && cur.y == ey) return cur.mirrors; // 도착하면 종료

            for (int i = 0; i < 4; i++) {
                int nx = cur.x + dx[i];
                int ny = cur.y + dy[i];
                int newMirrors = cur.mirrors + (cur.dir == i ? 0 : 1); // 방향이 바뀌면 거울 추가

                if (nx < 0 || ny < 0 || nx >= H || ny >= W || map[nx][ny] == '*') continue;
                if (visited[nx][ny][i] == 0 || visited[nx][ny][i] > newMirrors) {
                    visited[nx][ny][i] = newMirrors;
                    pq.offer(new Node(nx, ny, i, newMirrors));
                }
            }
        }

        return -1; // 도달 불가능한 경우
    }
}

---

⏱️ 시간 복잡도 분석

• BFS + 다익스트라 방식이므로 **O(W × H log(W × H))**의 시간 복잡도를 가진다.
• 맵의 크기가 최대 100 × 100 = 10,000 이므로, log(W × H)를 고려해도 충분히 빠르게 동작한다.
• 우선순위 큐를 사용하여 최소 거울 개수부터 탐색하므로, 불필요한 탐색을 줄일 수 있다.

---

💡 느낀점

✅ 단순한 BFS가 아닌, 최소한의 거울 설치 개수를 우선 탐색하는 방식을 고민해야 했다.
✅ **우선순위 큐(다익스트라)**를 활용하면 더 효율적인 탐색이 가능하다는 점이 중요했다.
✅ 방향별로 방문을 관리하는 **3차원 배열(visited[x][y][dir])**을 사용하는 것이 핵심이었다.
✅ 레이저 통신 문제는 전형적인 그래프 탐색 문제로, 유사 문제에도 적용할 수 있을 것 같다!

---

🎯 이 문제를 통해 BFS와 다익스트라를 결합하는 방법을 익힐 수 있었다! 🚀