백준 2151 (거울 설치) - java

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

2151번: 거울 설치

문제 :

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

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

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

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

 

유형 : BFS

 

접근

• 방향에 대한 정보도 유지해줘야 한다. -> 방문배열을 3차원으로 설정
• 현재 지점이 거울인 경우와 일반 땅인 경우를 나누어 처리하자
  • 거울인 경우 : 위나 아래 방향에서 오는 빛은 거울을 설치하지 않고 그대로 보낼 수 있고 왼쪽이나 오른쪽으로 거울을 설치하여 이동시킬 수 있다.
  • 일반 땅 : 들어온 방향에 대해서만 이동 가능하다.

전체 코드

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

public class Main {

    static int n = 0;
    static char[][] board;

    static int sx = 0;
    static int lx = 0;
    static int sy = 0;
    static int ly = 0;

    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        board = new char[n+1][n+1];
        boolean f = false;
        for(int i=1;i<=n;i++){
            String line = br.readLine();

            for(int j=1;j<=n;j++){
                board[i][j] = line.charAt(j-1);

                if(board[i][j] =='#'){
                    if(!f){
                        f = true;
                        sx = i;
                        sy = j;
                    }

                    else{
                        lx = i;
                        ly = j;
                    }
                }
            }
        }


        search();
        br.close();
    }

    static void search(){
        int result = 2501;
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sx,sy,-1));
        int[][][] visit = new int[n+1][n+1][4];
        visit[sx][sy][0]= 1;
        visit[sx][sy][1]= 1;
        visit[sx][sy][2]= 1;
        visit[sx][sy][3]= 1;

        while(!q.isEmpty()){
            Node cur = q.poll();
            if(cur.x == lx && cur.y == ly){
                result = Math.min(result,visit[lx][ly][cur.d] -1);
                continue;
            }

            if(board[cur.x][cur.y] == '#'){
                for(int i=0;i<4;i++){
                    int nx = cur.x + dx[i];
                    int ny = cur.y + dy[i];

                    if(nx < 1 || nx > n || ny < 1 || ny > n)
                        continue;

                    if(board[nx][ny] == '*')
                        continue;

                    if(visit[nx][ny][i] == 0 || visit[nx][ny][i] > visit[cur.x][cur.y][i]){
                        visit[nx][ny] = visit[cur.x][cur.y];
                        q.add(new Node(nx,ny,i));
                    }
                }
            }

            else if(board[cur.x][cur.y] == '!'){

                if(cur.d == 0 || cur.d == 1){
                    for(int i=2;i<4;i++){
                       int nx = cur.x + dx[i];
                       int ny = cur.y + dy[i];

                        if(nx < 1 || nx > n || ny < 1 || ny > n)
                            continue;

                        if(board[nx][ny] == '*')
                            continue;

                        if(visit[nx][ny][i] == 0 || visit[nx][ny][i] > visit[cur.x][cur.y][cur.d] + 1){
                            visit[nx][ny][i] = visit[cur.x][cur.y][cur.d] + 1;
                            q.add(new Node(nx,ny,i));
                        }
                    }

                    int nx = cur.x + dx[cur.d];
                    int ny = cur.y + dy[cur.d];

                    if(nx < 1 || nx > n || ny < 1 || ny > n)
                        continue;

                    if(board[nx][ny] == '*')
                        continue;

                    if(visit[nx][ny][cur.d] == 0 || visit[nx][ny][cur.d] > visit[cur.x][cur.y][cur.d]){
                        visit[nx][ny][cur.d] = visit[cur.x][cur.y][cur.d];
                        q.add(new Node(nx,ny,cur.d));
                    }
                }

                else{
                    for(int i=0;i<2;i++){
                        int nx = cur.x + dx[i];
                        int ny = cur.y + dy[i];

                        if(nx < 1 || nx > n || ny < 1 || ny > n)
                            continue;

                        if(board[nx][ny] == '*')
                            continue;

                        if(visit[nx][ny][i] == 0 || visit[nx][ny][i] > visit[cur.x][cur.y][cur.d] + 1){
                            visit[nx][ny][i] = visit[cur.x][cur.y][cur.d] + 1;
                            q.add(new Node(nx,ny,i));
                        }
                    }

                    int nx = cur.x + dx[cur.d];
                    int ny = cur.y + dy[cur.d];

                    if(nx < 1 || nx > n || ny < 1 || ny > n)
                        continue;

                    if(board[nx][ny] == '*')
                        continue;

                    if(visit[nx][ny][cur.d] == 0 || visit[nx][ny][cur.d] > visit[cur.x][cur.y][cur.d]){
                        visit[nx][ny][cur.d] = visit[cur.x][cur.y][cur.d];
                        q.add(new Node(nx,ny,cur.d));
                    }
                }
            }

            else if(board[cur.x][cur.y] == '.'){
                int nx = cur.x + dx[cur.d];
                int ny = cur.y + dy[cur.d];

                if(nx < 1 || nx > n || ny < 1 || ny > n)
                    continue;

                if(board[nx][ny] == '*')
                    continue;

                if(visit[nx][ny][cur.d] == 0 || visit[nx][ny][cur.d] > visit[cur.x][cur.y][cur.d]){
                    visit[nx][ny][cur.d] = visit[cur.x][cur.y][cur.d];
                    q.add(new Node(nx,ny,cur.d));
                }
            }
        }

        System.out.println(result);
    }
}
class Node{
    int x;
    int y;
    int d;

    Node(int x,int y,int d){
        this.x = x;
        this.y = y;
        this.d = d;
    }
}