6087 - 레이저 통신 (Java)

문제 개요 💡

문제에서는 격자판에 있는 두 개의 레이저 통신 지점(문자 C)을 연결하는 경로를 찾되,
경로 상에서 꺾이는 횟수(즉, 거울 사용 횟수)를 최소화하는 것이 목표입니다.
격자에는 벽(*)이 존재하여 이동이 제한되고, 레이저 빔은 한 방향으로 쭉 진행하다가
거울을 사용해 방향을 바꿀 수 있습니다.

---

접근 방법 🔍

이 문제는 너비 우선 탐색(BFS)를 통해 해결할 수 있습니다.
BFS를 사용하여 각 위치에 도달할 때까지 사용한 거울(방향 전환)의 최소 횟수를 관리하며 탐색합니다.

상태 정의 📝

각 BFS 노드는 다음 정보를 포함합니다:

• 현재 좌표 (x, y)
• 현재까지 사용한 거울(방향 전환) 횟수 cnt
• 현재 진행 방향 moveDir (상하좌우 0~3로 표현, 시작시에는 방향이 정해지지 않아 -1 사용)

방문 배열 📋

한 좌표에 도달하더라도 도착한 방향에 따라 이후 전개될 경로가 달라질 수 있습니다.
따라서, visited[x][y][dir] 형태의 3차원 방문 배열을 사용해
각 위치에 대해 4가지 방향별 최소 거울 사용 횟수를 기록합니다.

---

구현 시 고려했던 문제점과 수정 사항 ⚙️

1. 방문 조건 (Visited 조건) 비교 문제 🤔

초기 코드에서는

if (i == moveDir && visited[dx][dy] > cnt) { ... }
else if (i != moveDir && visited[dx][dy] > cnt + 1) { ... }

와 같이 ‘>’ 연산자로 방문 배열을 검사했습니다.

• 문제점:
  같은 거울 사용 횟수(cnt 또는 cnt + 1)로 도달하는 경우에도 방향이 다르면 이후 경로에 영향을 줄 수 있으므로,
  ‘>=’ 조건을 사용해 같은 값도 갱신해주어야 합니다.

수정된 코드는 다음과 같습니다:

if (i == moveDir && visited[dx][dy] >= cnt) {
    visited[dx][dy] = cnt;
    queue.add(new int[]{dx, dy, cnt, i});
} else if (i != moveDir && visited[dx][dy] >= cnt + 1) {
    visited[dx][dy] = cnt + 1;
    queue.add(new int[]{dx, dy, cnt + 1, i});
}

2. 역방향(뒤로 돌아가는) 이동 처리 🔄

초기에는 이전에 진행한 반대 방향으로 바로 돌아가는 경우를 제거하기 위해 아래 조건을 사용했습니다:

if ((moveDir + 2) % 4 == i) continue;

• 문제점:
  시작 상태에서는 moveDir이 -1이므로, 이 조건에서 계산 오류가 발생할 수 있습니다.

수정:
시작이 아닐 때만 역방향 체크를 적용하도록 수정합니다.

if (moveDir != -1 && (moveDir + 2) % 4 == i) continue;

3. 메모리 초과 문제 📈

초기에는 2차원 방문 배열을 사용했지만,
같은 좌표에 대해 방향별로 거울 사용 횟수가 달라질 수 있으므로 메모리 초과 문제가 발생했습니다.

해결책:
각 좌표마다 4가지 방향의 정보를 저장하기 위해 3차원 방문 배열을 사용합니다.

int[][][] visited = new int[N][M][4];

---

최종 알고리즘 요약 📌

1. 입력 처리

   • 격자 크기, 각 칸의 정보를 입력받습니다.
   • 첫 번째 C를 시작점으로, 두 번째 C는 도착점으로 처리하며, 시작점은 탐색 편의를 위해 '.'로 변경합니다.

2. BFS 초기화

   • 큐에 시작점을 넣습니다.
   • 방문 배열 visited는 모든 값을 Integer.MAX_VALUE로 초기화합니다.

3. BFS 수행

   • 현재 노드에서 4가지 방향으로 이동을 시도합니다.
   • 동일한 방향으로 이동 시 거울 사용 횟수를 그대로 유지하고,
     다른 방향으로 이동 시 거울 사용 횟수를 1 증가시킵니다.
   • 역방향 이동은 시작 상태가 아닐 경우 (moveDir + 2) % 4 == i 조건으로 차단합니다.
   • 방문 배열을 갱신하며, 더 적은 거울 횟수로 도달한 경우 해당 상태를 큐에 추가합니다.

4. 출력

   • 도착점에 도달했을 때의 최소 거울 사용 횟수에서,
     실제 거울이 설치된 횟수를 반영하기 위해 최종 값 - 1을 출력합니다.

---

최종 코드 예시 💻

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

public class Main {
    private static int N, M;
    private static char[][] map;
    private static int sx = -1, sy = -1;
    private static int[][] dir = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    public static void main(String[] args) throws IOException {
        inputSetting();
        System.out.println(getAnswerByBfs());
    }
    
    private static int getAnswerByBfs() {
        int answer = Integer.MAX_VALUE;
        Queue<int[]> queue = new ArrayDeque<>();
        int[][][] visited = new int[N][M][4];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }
        
        // 초기 상태: 시작점의 방향은 정해지지 않았으므로 -1 사용
        queue.add(new int[]{sx, sy, 0, -1});
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], cnt = cur[2], moveDir = cur[3];
            
            // 도착점에 도달한 경우 최소 거울 사용 횟수 갱신
            if (map[x][y] == 'C') {
                answer = Math.min(answer, cnt);
            }
            
            for (int i = 0; i < 4; i++) {
                // 시작이 아닌 경우 역방향(바로 뒤로 가는) 이동은 제외
                if (moveDir != -1 && (moveDir + 2) % 4 == i) continue;
                
                int dx = x + dir[i][0];
                int dy = y + dir[i][1];
                
                if (dx < 0 || dx >= N || dy < 0 || dy >= M) continue;
                if (map[dx][dy] == '*') continue;
                
                // 같은 방향이면 거울 추가 없이, 다른 방향이면 거울 1개 추가
                if (moveDir == i && visited[dx][dy][i] >= cnt) {
                    visited[dx][dy][i] = cnt;
                    queue.add(new int[]{dx, dy, cnt, i});
                } else if (moveDir != i && visited[dx][dy][i] >= cnt + 1) {
                    visited[dx][dy][i] = cnt + 1;
                    queue.add(new int[]{dx, dy, cnt + 1, i});
                }
            }
        }
        return answer - 1;
    }
    
    private static void inputSetting() 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());
        map = new char[N][M];
        for (int i = 0; i < N; i++) {
            String inputString = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = inputString.charAt(j);
                if (sx == -1 && map[i][j] == 'C') {
                    sx = i;
                    sy = j;
                    map[i][j] = '.';
                }
            }
        }
    }
}

---

반례 및 수정 기록 📝

문제를 해결하는 과정에서 여러 반례를 만나며 다음과 같이 수정했습니다:

1. 방문 조건 수정

   • 기존에 visited[dx][dy] > cnt로만 비교했으나,
     동일한 값일 경우도 방향에 따라 달라질 수 있으므로 >=로 변경하였습니다.

2. 역방향 이동 체크 수정

   • 초기 시작 상태에서 moveDir이 -1일 때 (moveDir + 2) % 4 계산에서 오류가 발생하므로,
     if (moveDir != -1 && (moveDir + 2) % 4 == i) continue;로 조건문을 추가하였습니다.

3. 메모리 초과 문제 해결

   • 동일 좌표의 방문 여부를 단순 2차원 배열로 관리하다가 메모리 초과가 발생하여,
     방향 정보를 포함한 3차원 배열로 변경하였습니다.

이러한 수정 과정을 통해 최종적으로 올바른 풀이를 완성할 수 있었습니다. 🎉

---