[BOJ] 백준 2151 : 거울 설치 (java)

🧪 2151 거울 설치

---

난이도 : 🌟 골드 3
유형 : BFS

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

 

📝 문제

---

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

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

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

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

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

 

 

입력

 

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

 

출력

 

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

 

🧐 핵심 로직 

---

1) 출발하는 문(#)을 저장해두고 출발할 수 있는 방향을 우선순위 큐에 넣어둔다.

    1 - a) 출발하는 문은 중복되지 않게 *으로 초기화해둔다.

 

2) 방문 체크 배열(visited)를 int형으로 선언해두고 -1로 초기화 시킨다(거울을 사용하지 않을 경우도 있기 때문에 -1로 초기화)

 

3) bfs 알고리즘을 동작 시키면서 거울을 놓을 수 있는 곳(!)일 경우, 방향을 현재방향에서 시계, 반시계 방향 90도로 돌리고 cnt를 하나 높이고 큐에 넣어준다.

 

4) ! or . 일 경우 모두 현재 방향 기준으로 전진시켜서 큐에 넣어준다.

 

5) 목적지(#)에 도착한 경우 cnt를 출력해주고 함수를 종료시킨다.

    5 - a) PriorityQueue를 사용했기 때문에 거울을 최소로 사용한 경우가 보장된다.

 

💻 최종 코드 (152 ms)

---

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

public class Main {

    static class Node implements Comparable<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;
        }

        @Override
        public int compareTo(Node o) {
            return this.cnt - o.cnt;
        }
    }

    static int n, res;
    static Node startNode;
    static PriorityQueue<Node> pq;
    static int[][] visited;
    static char[][] houseMap;
    static int[] dx = { -1, 0, 1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedReader br = new BufferedReader(new FileReader("input.txt"));

        n = Integer.parseInt(br.readLine());

        visited = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(visited[i], -1);
        }

        houseMap = new char[n][n];
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            for (int j = 0; j < n; j++) {
                houseMap[i][j] = str.charAt(j);

                if (houseMap[i][j] == '#') {
                    startNode = new Node(i, j, 0, 0);
                }
            }
        }

        houseMap[startNode.x][startNode.y] = '*';

        pq = new PriorityQueue<>();
        for (int i = 0; i < 4; i++) {
            int nx = startNode.x + dx[i];
            int ny = startNode.y + dy[i];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || houseMap[nx][ny] == '*') continue;
            pq.offer(new Node(startNode.x, startNode.y, i, 0));
        }

        bfs();
        System.out.println(res);

        br.close();
    }

    private static void bfs() {

        visited[startNode.x][startNode.y] = 0;

        while (!pq.isEmpty()) {
            Node curNode = pq.poll();

            if (houseMap[curNode.x][curNode.y] == '#') {
                res = curNode.cnt;
                return;
            }

            int nx = curNode.x + dx[curNode.dir];
            int ny = curNode.y + dy[curNode.dir];

            if (nx < 0 || ny < 0 || nx >= n || ny >= n || houseMap[nx][ny] == '*') continue;
            if (visited[nx][ny] >= curNode.cnt) continue; // pq를 통해서 이미 최소의 거울 개수를 구하고 있기 때문에 현재의 cnt가 visited보다 크거나 같은 부분은 의미가 없다.

            visited[nx][ny] = curNode.cnt;

            if (houseMap[nx][ny] == '!') {
                pq.offer(new Node(nx, ny, (curNode.dir+1)%4, curNode.cnt+1));
                pq.offer(new Node(nx, ny, (curNode.dir+3)%4, curNode.cnt+1));
            }

            pq.offer(new Node(nx, ny, curNode.dir, curNode.cnt));
        }
    }
}