[백준] 6087 - 레이저 통신 (자바 Java)

[Gold III] 레이저 통신 - 6087

문제 링크

성능 요약

메모리: 39540 KB, 시간: 264 ms

분류

너비 우선 탐색(bfs), 다익스트라(dijkstra), 그래프 이론(graphs), 그래프 탐색(graph_traversal)

문제 설명

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

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

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

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

7 . . . . . . .         7 . . . . . . .
6 . . . . . . C         6 . . . . . /-C
5 . . . . . . *         5 . . . . . | *
4 * * * * * . *         4 * * * * * | *
3 . . . . * . .         3 . . . . * | .
2 . . . . * . .         2 . . . . * | .
1 . C . . * . .         1 . C . . * | .
0 . . . . . . .         0 . \-------/ .
  0 1 2 3 4 5 6           0 1 2 3 4 5 6

입력

첫째 줄에 W와 H가 주어진다. (1 ≤ W, H ≤ 100)

둘째 줄부터 H개의 줄에 지도가 주어진다. 지도의 각 문자가 의미하는 것은 다음과 같다.

• .: 빈 칸
• *: 벽
• C: 레이저로 연결해야 하는 칸

'C'는 항상 두 개이고, 레이저로 연결할 수 있는 입력만 주어진다.

출력

첫째 줄에 C를 연결하기 위해 설치해야 하는 거울 개수의 최솟값을 출력한다.

 

---

풀이

항상 접근방식까지는 생각할 수 있는데, 디테일에서 실수가 많아 걱정이다.. 로직을 완벽하게 짜는 것도 어렵고 세세한 테케를 생각해내는 게 어려운 것 같다

 

아무튼 bfs를 활용해서 풀었다. 여기서는 단순히 이차원배열에 방문처리를 하면 안된다는 것이 핵심이다.

 

처음에는 방향별로 3차원 배열을 만들어서 방문처리를 하였다. 그런데 여러 방향에서 방문하다 보니 네 방향으로 나누어도 이미 방문한 위치에 대해 더 짧은 비용으로 방문하는 경우가 생겼다. 

처음에는 boolean 배열로 만들어서 이 경우를 처리하기가 까다로웠고, int 배열로 바꿔서 각각의 비용을 방문 배열에 저장하였다.

그리고 visited 배열의 값이 0이거나, 배열의 값이 현재 비용보다 크거나 같은 경우 (같은 경우를 빼면, 다음 경로를 탐색할 때 최소값을 포함하지 않는 문제가 생김) 에만 queue에 새로 값을 추가하도록 했다.

 

또한 시작값을 다시 방문하지 않게 하려고 시작점의 방문 배열의 값도 따로 처리해준다.

for (int d = 0; d < 4; d++)
    visited[start[0]][start[1]][d] = 1; // start로 다시 가지 않도록

그리고 queue에 추가할 때 방문처리를 해줘야 시간을 줄일 수 있다. 

for (int dir = 0; dir < 4; dir++) {
    int nr = r + dr[dir];
    int nc = c + dc[dir];

    if (nr >= 0 && nr < R && nc >= 0 && nc < C && map[nr][nc] != '*' && (visited[nr][nc][dir] == 0 || visited[nr][nc][dir] > cnt)) {
        // 방문 처리 여기서하기 -> 시간 절약

        if (dir == d) {
            visited[nr][nc][dir] = cnt;
            q.add(new int[]{nr, nc, dir, cnt});
        } else {
            visited[nr][nc][dir] = cnt + 1;
            q.add(new int[]{nr, nc, dir, cnt + 1});
        }
    }

}

 

전체 코드

package BOJ.Gold.g3;

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

public class BOJ_6087_레이저통신 {
    static int C, R;
    static char[][] map;
    static int[][][] visited; // 방향까지 저장
    static int[] dr = {1, -1, 0, 0};
    static int[] dc = {0, 0, 1, -1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        C = Integer.parseInt(st.nextToken());
        R = Integer.parseInt(st.nextToken());
        int[] start = new int[2];
        Arrays.fill(start, -1);
        int[] end = new int[2];
        map = new char[R][C];
        for (int i = 0; i < R; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < C; j++)
                if (map[i][j] == 'C') {
                    if (start[0] == -1) {
                        start[0] = i;
                        start[1] = j;
                    } else {
                        end[0] = i;
                        end[1] = j;
                    }
                }
        }

        // 삼차원 배열 -> 이전 방향이 어떤 방향이었는지 체크함
        visited = new int[R][C][5];
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{start[0], start[1], 4, 0}); // r, c, 방향, 거울 수
        for (int d = 0; d < 4; d++)
            visited[start[0]][start[1]][d] = 1; // start로 다시 가지 않도록
        /*
        4 5
        C..*
        ...*
        ...*
        *.**
        ...C

         */

        int ans = Integer.MAX_VALUE;
        while (!q.isEmpty()) {
            int[] node = q.poll();

            int r = node[0];
            int c = node[1];
            int d = node[2];
            int cnt = node[3];


            if (r == end[0] && c == end[1]) {
                ans = Math.min(ans, cnt);
                continue;
            }


            for (int dir = 0; dir < 4; dir++) {
                int nr = r + dr[dir];
                int nc = c + dc[dir];

                if (nr >= 0 && nr < R && nc >= 0 && nc < C && map[nr][nc] != '*' && (visited[nr][nc][dir] == 0 || visited[nr][nc][dir] > cnt)) {
                    // 방문 처리 여기서하기 -> 시간 절약

                    if (dir == d) {
                        visited[nr][nc][dir] = cnt;
                        q.add(new int[]{nr, nc, dir, cnt});
                    } else {
                        visited[nr][nc][dir] = cnt + 1;
                        q.add(new int[]{nr, nc, dir, cnt + 1});
                    }
                }

            }

        }
        System.out.println(ans - 1); // 맨처음 방향 바꾼건 빼기
    }
}