BOJ - 거울 설치 2151번 (JAVA)

❓ 문제 - 백준 거울 설치 2151번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/2151)

2151번: 거울 설치

 

 

 

📝 문제해결법

1. 문제 해석

• 하나의 문(#)에서 출발하여 다른 문(#)까지 도착할 수 있게 이동할 수 있어야 한다.
• 거울(!)을 설치할 수 있는 위치에서 거울을 설치하면 45도 방향으로 이동 방향을 바꿀 수 있다.
• 거울을 최소한 설치해서 하나의 문에서 다른문 까지 도착할 수 있도록 할 때, 최소 설치 거울의 갯수를 구하여라.

 

2. 이 문제는 BFS(너비 우선 탐색)으로 해결하였습니다.

• Node는 위치 x, y ,현재 이동방향 dir, 설치한 거울 수 cnt로 나타낸다.
• 두 문(#) 중 하나의 문에서 BFS를 하도록 하며, 큐에서 4방향(북,남,서,동)으로 이동할 수 있게 넣어준다.
• visited는 방문체크 배열인데 큐에서 이동하면서 해당 위치(x,y)와 방향(dir)에 맞춰 현재까지 설치한 거울 수를 배열에 저장한다.
• 큐에서 너비우선탐색으로 진행하며, 이동할 방향(nx, ny)의 범위가 가능한지, 벽이 아닌지, 이동하려는 방향에 설치한 거울 수가 더 적은 상태로 이미  방문을 했는지를 체크해준 후 continue 처리한다.
• 만약 이동할 곳이 빈 곳(.) 이라면 현재 이동방향 그대로 큐에 넣어 이동처리한다.
• 만약 이동할 곳이 거울이 설치할 수 있는 위치(!) 라면 거울을 설치 안 하고 지나가는 경우, 거울을 설치하고 지나가는 경우로 나눈다.
  • 거울을 설치할 때 현재 진행 방향이 북, 남이면 45도로 방향을 변경할 수 있으므로  동, 서로 방향을 바꿀 수 있다.
  • 거울을 설치할 때 현재 진행 방향이 동, 서이면 45도로 방향을 변경할 수 있으므로 북, 남으로 방향을 바꿀 수 있다.
• 만약 이동할 곳이 문(#)이면 도착이므로 현재 이동할 때까지 설치한 거울 수의 최솟값을 갱신한다.

 

3. 느낀점 & 삽질

1) visited를 boolean으로 그냥 그 위치와 방향에 방문 했으면 방문하지 못하도록 구현했으나..

20 #.....!.!........... ******.*.*********** *!....!*.*********** *.****.*.*********** *.**!.!*.*********** *.**.***.*********** *.**!.!*.*********** *.****.*.*********** *.**!.!*.*********** *.**.***.*********** *!..!.......#******* ********.***.******* ********.***.******* ********.***.******* ********.***.******* ********.*!.!******* ********.*.********* ********.*!.!******* ********.***.******* ********!...!*******

와 같은 테케에서 답이 4가 나와야 하는데 7이 나왔다.

 

알고보니 큐에 먼저 설치한 거울 수가 많은 노드가 먼저 들어가서 방문처리 되었는데, 큐에 뒤에 있는 노드가 위치와 방향이 같은데 설치한 거울 수가 더 적으면 이미 방문처리 되어 큐에 들어가지 못해 최솟값에 영향을 준다.

 

따라서 int 배열로 바꿔 방문체크를 하였고, 배열 안에 현재 위치, 방향으로 이동까지 설치한 에어컨의 수보다 내가 지금 이동 하면서 설치한 에어컨의 수가 적을 때만 방문할 수 있도록 로직을 바꾸었고 잘 작동하였다.

 

2) BFS 문제의 경우 이런 큐에 먼저들어가고 방문처리와 관련해서 많은 문제들이 존재하는데

이런 부분까지 조심해서 로직을 구현해야겠다고 생각했다...

 

오랜만에 BFS를 푸니 재밌다....!

 

 

 

💻 소스코드 (JAVA)

// BOJ - 거울설치(2151번)
// BFS
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main_2151 {
    public static int n;
    public static int min_value;
    public static class Node {
        int x;
        int y;
        int dir;
        int cnt;
        public Node(int x, int y, int dir, int cnt){
            this.x = x;
            this.y = y;
            this.dir = dir;
            this.cnt = cnt;
        }
    }
    public static int sx, sy;
    // 하, 상, 좌, 우
    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};
    public static char[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new char[n][n];

        for(int i=0;i<n;i++){
            map[i] = br.readLine().toCharArray();
            for(int j=0;j<n;j++){
                if(map[i][j] == '#'){
                    sx = i;
                    sy = j;
                }
            }
        }
        min_value = Integer.MAX_VALUE;
        bfs();
        System.out.println(min_value);
    }

    public static void bfs(){
        int[][][] visited = new int[n][n][4];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                Arrays.fill(visited[i][j], Integer.MAX_VALUE);
            }
        }

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sx, sy, 0, 0));
        q.add(new Node(sx, sy, 1, 0));
        q.add(new Node(sx, sy, 2, 0));
        q.add(new Node(sx, sy, 3, 0));
        visited[sx][sy][0] = 0;
        visited[sx][sy][1] = 0;
        visited[sx][sy][2] = 0;
        visited[sx][sy][3] = 0;

        while (!q.isEmpty()){
            int q_len = q.size();
            for(int i=0;i<q_len;i++){
                Node node = q.poll();
                int nx = node.x + dx[node.dir];
                int ny = node.y + dy[node.dir];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny][node.dir] < node.cnt || map[nx][ny] == '*') continue;

                if(map[nx][ny] == '.'){
                    visited[nx][ny][node.dir] = node.cnt;
                    q.add(new Node(nx, ny, node.dir, node.cnt));
                } else if(map[nx][ny] == '!'){
                    visited[nx][ny][node.dir] = node.cnt;
                    if(node.dir <= 1){
                        visited[nx][ny][2] = node.cnt;
                        visited[nx][ny][3] = node.cnt;
                        q.add(new Node(nx, ny, node.dir, node.cnt));
                        q.add(new Node(nx, ny, 2, node.cnt+1));
                        q.add(new Node(nx, ny, 3, node.cnt+1));
                    } else {
                        visited[nx][ny][0] = node.cnt;
                        visited[nx][ny][1] = node.cnt;
                        q.add(new Node(nx, ny, node.dir, node.cnt));
                        q.add(new Node(nx, ny, 0, node.cnt+1));
                        q.add(new Node(nx, ny, 1, node.cnt+1));
                    }
                } else if(map[nx][ny] == '#'){
                    min_value = Math.min(min_value, node.cnt);
                }

            }
        }

    }
}