2151번 : 거울 설치 [JAVA]

문제

채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.

채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.

채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.

거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.

거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.

입력

첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.

출력

첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.

예제 입력 1

5
***#*
*.!.*
*!.!*
*.!.*
*#***

예제 출력 1

2

성공 여부(걸린 시간): 성공(45분 22초)

아이디어

이 문제 또한 친구가 추천해주어서 풀게 되었는데 이전에 내가 풀었던 레이저 통신이라는 문제와 매우 유사함을 느꼈다.
유사한 유형의 레이저통신 풀이 링크
하지만 푼지 꽤되어서 가물가물하여 저번에는 단번에 성공하지 못한 문제였기에 차근차근 생각하며 다시 풀게된 좋은 계기가 되었다.

BFS + 방향의 정보를 내포하는 3차원 방문처리 배열이 난 이 로직의 핵심이라고 생각한다.

우선 문들의 좌표를 저장하고 있는 doors라는 ArrayList int[]형 배열을 만들어주고 시작과 끝지점을 활용하기 쉽게 해주었다.
그리고 방문처리는 3차원 배열로 각 하우상좌 (상하좌우 하좌우상 아무렇게 해도 상관없음) 방향에 대한 그 좌표에 도달하기 까지의 설치한 최소 거울 설치 횟수를 저장해준다. 난 이게 포인트라고 생각한다. 방향에 따라 저장을 하지 않고 단순하게 2차원 배열로 저장을 했다면 그것은 앞뒤 시점에서의 방향에 대한 정보를 알 수가 없다. 이전의 뱡향을 알아야 바꾸고 나서 cnt+1한 값과 비교를 하고 처리들을 해주니 코드를 보면 알겠지만 필수적인 요소라고 생각한다. 이때문에 우선순위 큐만 안썼을 뿐 다익스트라의 향(distance 배열 관리와 이전 이후값의 비교들이 존재하기에)도 느껴지는 코드라고 생각된다.

이 외에는 그냥 단순히 BFS를 돌아주면 된다.

• 기본적으로 '.'일때는 최선이면서 갈 수 있다면 직진을 해주지만
• '!'에 도달했을때는 거울을 설치할 수 있다. 따라서 그때는 추가적으로 방향을 틀 수 있는 2 가지 상황이 visited 배열에 cnt 수를 근거로 하여 최선이라는 조건이 만족한다. => 그렇다면 바뀐 방향과 cnt+1를 cnt로 가지는 노드를 큐에 넣어준다.

그렇게 도달한 최종 노드의 cnt중 최소값을 출력해주면 끝!

정답 코드

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

class Main {
    static int N;
    static class Node{
        int x, y, dir, cnt;
        Node(int x, int y, int dir, int cnt){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int [][] map = new int[N][N];
        int [] dx = {1, 0, -1, 0};//하 우 상 좌
        int [] dy = {0, 1, 0, -1};
        ArrayList<int[]> doors = new ArrayList<>();//문들의 위치를 저장함
        for(int i=0; i<N; i++){
            String input = br.readLine();
            for(int j=0; j<N; j++){
               char x = input.charAt(j);
               if(x=='#'){
                   doors.add(new int [] {i,j});
               }
               map[i][j] = x=='#'?'.':x; //문일 경우에 .으로 저장, 어차피 *과 범위 밖만 아니면 전부 갈 수 있음.
            }
        }
        //최소한의 거울을 설치 === 방향전환을 최소화
        ArrayDeque<Node> q = new ArrayDeque<>();
        int [][][] visited = new int[N][N][4];// 해당칸에서의 방향에 따른 최소거울개수 저장하고 있음
        for(int i=0; i<N; i++){
            for(int j=0; j<N; j++){
                for(int k =0; k<4; k++){
                    visited[i][j][k] = -1;
                }
            }
        }
        for(int i =0; i<4; i++){
            q.add(new Node(doors.get(0)[0],doors.get(0)[1], i, 0));
            visited[doors.get(0)[0]][doors.get(0)[1]][i] = 0;
        }
        int result = Integer.MAX_VALUE;
        int [] reflect = {1, 3}; // 이렇게 더 해주고 4의 나머지를 구하면 방향이 거울의 설치 경우의 수 2가지에 만족하는 방향으로 변경된다.
        while (!q.isEmpty()){
            Node cur = q.poll();
            int x = cur.x;
            int y = cur.y;
            int dir = cur.dir;
            int cnt = cur.cnt;
            if(x==doors.get(1)[0] && y ==doors.get(1)[1]){//도착한 경우
                result = Math.min(result, cnt);
                continue;
            }
            else if(map[x][y]=='!'){//거울설치 가능
                //하 우 상 좌 순서임
                for(int mv_dir: reflect){
                    int mdir = (dir+mv_dir)%4;
                    int mx = x+dx[mdir];
                    int my = y+dy[mdir];
                    //바꾼 방향의 cnt+1이 이전 방문 기록보다 작으면 최신화와 함께 큐에 넣어줌
                    if(canGo(mx, my)&&(visited[mx][my][mdir]==-1|| cnt+1<visited[mx][my][mdir])&&map[mx][my]!='*'){
                        visited[mx][my][mdir] = cnt+1;
                        q.add(new Node(mx, my, mdir, cnt+1));
                    }
                }
            }
            //그냥 직진할때도 처리해줌
            int sx = x+dx[dir];
            int sy = y+dy[dir];
            // 직진할 수 있는 경우에 이전 방문기록보다 작아야 큐에 넣어줌과 방문기록 최신화를 해줄 수 있음
            if(canGo(sx, sy)&&(visited[sx][sy][dir]==-1||visited[sx][sy][dir]>cnt)&&map[sx][sy]!='*'){
                visited[sx][sy][dir] = cnt;
                q.add(new Node(sx, sy, dir, cnt));
            }
        }
        System.out.print(result);
    }
    static boolean canGo(int x, int y){
        return  x>=0&&y>=0&&x<N&&y<N;
    }
}

성공~