[백준]#2151 거울 설치

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

2

풀이

이 문제는 BFS 알고리즘을 이용해서 풀 수 있는 문제였으나 문제 해석에서 조금 애를 먹었다. 문제를 정확하게 이해한다면 크게 어렵지 않은 난이도였다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Main {
    static ArrayList<Pair> doors = new ArrayList<>();
    static int N;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    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++) {
            String input = br.readLine();
            for(int j=0; j<N; j++) {
                map[i][j] = input.charAt(j);
                if(map[i][j]=='#')
                    doors.add(new Pair(i, j, -1, 0));
            }
        }

        bfs();
    }

    public static void bfs() {
        Queue<Pair> queue = new LinkedList<>();
        boolean[][] visited = new boolean[N][N];
        visited[doors.get(0).x][doors.get(0).y] = true;

        for(int i=0; i<4; i++) {
            if(doors.get(0).x+dx[i]>=0 && doors.get(0).x+dx[i]<N && doors.get(0).y+dy[i]>=0 && doors.get(0).y+dy[i]<N && map[doors.get(0).x+dx[i]][doors.get(0).y+dy[i]] != '*')
                queue.add(new Pair(doors.get(0).x, doors.get(0).y, i, 0));
        }

        while(!queue.isEmpty()) {
            Pair temp = queue.poll();
            int j = 1;

            while(true) {
                int nx = temp.x + j*dx[temp.d];
                int ny = temp.y + j*dy[temp.d];

                if(nx<0 || nx>=N || ny<0 || ny>=N || visited[nx][ny] || map[nx][ny]=='*') break;

                if(nx==doors.get(1).x && ny==doors.get(1).y) {
                    System.out.println(temp.cnt);
                    return;
                }

                if(map[nx][ny]=='!') {
                    if(temp.d==0 || temp.d==1) {
                        queue.add(new Pair(nx, ny, 2, temp.cnt+1));
                        queue.add(new Pair(nx, ny, 3, temp.cnt+1));
                    }

                    else {
                        queue.add(new Pair(nx, ny, 0, temp.cnt+1));
                        queue.add(new Pair(nx, ny, 1, temp.cnt+1));
                    }
                }

                j++;
            }
        }
    }

    public static class Pair {
        int x;
        int y;
        int d;
        int cnt;

        public Pair(int x, int y, int d, int cnt) {
            this.x = x;
            this.y = y;
            this.d = d;
            this.cnt = cnt;
        }
    }
}