BOJ G3 2151 거울 설치 JAVA

2151번: 거울 설치

---

문제 읽기

처음에 문제를 읽었을 때에는 dfs를 써야겠다고 생각했다. 그렇게 풀었는데 백트래킹을 제대로 하지 않아서 인지.. 3%에서 계속 시간 초과가 났다 !! 너무 답답해서 그냥 풀이 방식을 바꿔보기로 했다.

글 읽기 - 어디가 틀렸을까요 ㅠ

위 글을 통해 힌트를 얻었다. 0-1 BFS를 이용하면 될 것 같았다. 잊고 있었던 알고리즘이다.

---

문제 풀기

0-1 BFS는 BFS처럼 방문하면서, Deque를 이용하여 방문 비용이 증가하면 뒤에 넣고, 그대로이면 앞에 넣으며 이동한다. 또한 방문 체크를 덱에서 꺼낼 때 하기 때문에 같은 지점에 대해서 여러 번 값을 덱에 넣어 두고, 그 중에서 최소 비용으로 방문할 수 있다. (즉, 중복 방문이 가능하며, 그 중 최솟값을 저장할 수 있는 방식이다.) 이 특징은 다익스트라와 유사하다.

사실 다익스트라와 0-1 BFS는 진짜 한 끗 차이라 생각한다.. 진짜 비슷하다. 차이점은 방문 체크, 자료구조, 삽입 방식 뿐이다.

 

처음에는 중복 방문 때문에 DFS가 더 와 닿았는데, 최소 비용이기 때문에 DFS보다는 BFS를 하는 게 훨씬 효율적이라는 생각이 든다.

 

다익스트라에 대한 자세한 설명을 보고 싶으면 아래 링크를 방문하면 된다.

다익스트라, Dijkstra Algorithm

 

0-1 BFS에 대한 자세한 설명을 보고 싶으면 아래 링크를 방문하면 된다.

0-1 BFS

 

사실 원래 0-1 BFS는 비용이 갱신 되는 경우에만 방문하기 때문에 따로 방문 체크를 하지 않아도 별 문제는 없었다. 하지만 이 문제의 경우에는 따로 갱신할 비용이 없기 때문에 방문 처리를 해주는 식으로 메모리와 시간을 줄였다. (어찌 보면 다익스트라에 더 가까울지도)

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class BOJ_G3_2151_거울설치 {
    static class Pos{
        int r, c;
        int cnt;
        int dir;
        public Pos(int r, int c, int cnt, int dir){
            this.r = r;
            this.c = c;
            this.cnt = cnt;
            this.dir = dir;
        }
    }
    static int N;
    static char[][] map;
    static boolean[][][] visited;
    static int startR = -1, startC, endR, endC;
    static int[] dr = {-1, 0, 1, 0};//상0좌1하2우3 -> 0101
    static int[] dc = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(in.readLine());
        map = new char[N][N];
        for (int i = 0; i < N; i++){
            map[i] = in.readLine().toCharArray();
            for (int j = 0; j < N; j++){
                if (map[i][j] == '#'){
                    if (startR == -1){
                        startR = i;
                        startC = j;
                    }
                    else{
                        endR = i;
                        endC = j;
                    }
                }
            }
        }

        Deque<Pos> dec = new ArrayDeque<>();
        visited = new boolean[N][N][4];
        for (int di = 0; di < 4; di++){
            int nr = startR + dr[di];
            int nc = startC + dc[di];
            if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == '*') continue;
            dec.offer(new Pos(nr, nc, 0, di));
        }

        while(!dec.isEmpty()){
            Pos cur = dec.pollFirst();
//            System.out.println(cur.r + " " + cur.c);
            if (visited[cur.r][cur.c][cur.dir]) continue;
            visited[cur.r][cur.c][cur.dir] = true;

            if (cur.r == endR && cur.c == endC){
                System.out.println(cur.cnt);
                break;
            }
            else if (map[cur.r][cur.c] == '.'){
                //직진
                int nr = cur.r + dr[cur.dir];
                int nc = cur.c + dc[cur.dir];
                if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == '*') continue;
                dec.offerFirst(new Pos(nr, nc, cur.cnt, cur.dir));
            }
            else { //느낌표인 경우 -> 3방향
                for (int di = 0; di < 4; di++){
                    if (di == (cur.dir + 2)%4) continue;
                    int nr = cur.r + dr[di];
                    int nc = cur.c + dc[di];
                    if (nr < 0 || nr >= N || nc < 0 || nc >= N || map[nr][nc] == '*') continue;

                    if (di == cur.dir){
                        dec.offerFirst(new Pos(nr, nc, cur.cnt, cur.dir));
                    }
                    else{
                        dec.offerLast(new Pos(nr, nc, cur.cnt+1, di));
                    }
                }
            }
        }
    }
}