백준 6087번 <레이저 통신>

백준 알고리즘 6087번

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

6087번: 레이저 통신

---

6087번

크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다.

'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다.

레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다.

아래 그림은 H = 8, W = 7인 경우이고, 빈 칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다.

---

문제 해결

어떻게 문제를 풀어야 하는지 감이 안 잡혔는데, 거울을 설치한다고 생각하는게 아니라 몇 번 꺾여야 하는지로 접근하니까 실마리가 잡혔다.

 

하나의 C에서 다른 C로 가는 모든 경로를 확인하며, 몇 번 꺾이는지를 체크해줬다.

경로가 길어도 꺾이는 횟수가 적을 수 있기 때문에 모든 경로를 확인해야 한다고 생각했고 그래서 DFS를 사용해 문제를 풀었다.

 

W와 H의 최댓값이 100으로 작아서 처음엔 모든 경로를 확인하기 위해 DFS 함수에 방문 체크 배열을 모두 가지고 다녔는데 시간이 오래 걸렸다.

 

그래서 다음엔 static 변수로 방문 체크 배열을 선언해서 문제를 풀이했다.

방문 체크 배열을 int 형 2차원 배열로 만들어서 하나의 C에서 각 좌표로 갈 때 적게 꺾여서 가는 횟수를 저장해두었다. 그래서 방문 체크 배열에 저장된 횟수보다 덜 꺾여서 가면 방문을 열어주었다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class BOJ_6087 {
    static int N, M, ans;
    static int[] start, end;
    static int[] di = {-1, 1, 0, 0};
    static int[] dj = {0, 0, -1, 1};
    static char[][] Board;
    static int[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] inArr = br.readLine().split(" ");
        M = Integer.parseInt(inArr[0]);
        N = Integer.parseInt(inArr[1]);
        Board = new char[N][M];
        start = new int[2];
        end = new int[2];
        boolean flag = false;
        for (int i = 0; i < N; i++) {
            Board[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (Board[i][j] == 'C') {
                    if (!flag) {
                        start = new int[]{i, j};
                        flag = true;
                    } else {
                        end = new int[]{i, j};
                    }
                }
            }
        }
        // end input

        // start -> end 로 가는 경로에서 꺾이는 부분의 개수 세기
        ans = Integer.MAX_VALUE;
        for (int k = 0; k < 4; k++) {
            visit = init();
            DFS(start[0],start[1], k, 0);
        }
        System.out.println(ans);
    }

    static void DFS(int I, int J, int D, int cnt) {
        if (cnt >= ans) return;  // 이미 정답보다 횟수가 많으면 볼 필요 없음
        if (I == end[0] && J == end[1]) {
            ans = Math.min(ans, cnt);
            return;
        }
        visit[I][J] = cnt;
        for (int k = 0; k < 4; k++) {
            int ni = I + di[k];
            int nj = J + dj[k];
            if (ni < 0 || nj < 0 || ni >= N || nj >= M || visit[ni][nj] <= cnt || Board[ni][nj] == '*') continue;

            if (k == D) {
                DFS(ni, nj, k, cnt);
            } else {
                DFS(ni, nj, k, cnt+1);
            }
        }
    }
    static int[][] init() {
        int[][] visit = new int[N][M];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                visit[i][j] = Integer.MAX_VALUE;
            }
        }
        return visit;
    }
}

---

결과

---

코드를 작성하면서 느낀 것인데, 

방문 체크 배열의 값이 더 작은 경우만 걸러주는 것이 아니라 같은 경우도 걸러주어야 한다. 

또한 ans의 값을 가지고 체크를 할 때, cnt가 큰 경우만 걸러주는 것이 아니라 같은 경우도 걸러주어야 한다.