[JAVA] 백준 2151 : 거울 설치

문제

2151번: 거울 설치

 

해결 방법

 

빛은 일직선으로 나아가고, 45도 각도의 거울을 사용해서 이동방향을 바꿔 목적지에 도착하도록 하는 문제이다.

그래서 현재 방향이 어디인지 저장할 dir을 사용하고, cnt를 사용해서 거울을 몇 번 사용했는지 체크하게끔 class를 구성했다.또 우선순위 큐를 사용해서 가장 거울을 적게 사용한 결괏값이 제일 먼저 목적지에 도착하도록 하였다.

 

시작점과 도착점이 문제와 같이 2개만 주어지는 문제는 처음 입력을 받을 때 해당 지점을 체크해두고 푸는 방식을 자주 사용했다.위 문제에서 보면 시작점과 도착점을 '#'으로 표시하는데 입력을 받을 때 '#'의 지점을 startX, startY에 저장해둔 뒤남은 '#' 을 찾아가는 방향으로 푸는 방식이다.그래서 startX, startY 지점은 '.'으로 추후에 초기화를 시켜 map 배열에 '#'이 하나만 존재하게 만들었다.

 

방문 배열은 4방향에 따라 체크를 하기 위해 3차원 배열을 사용했고,시작점은 모든 방향에서 모두 true로 해서 방문 설정을 하였다.

 

또 처음 시작하는 곳에서 어느 방향으로 빛이 나아갈 수 있는지 체크해야 하기 때문에,첫 시작점의 방향을 상관없는 숫자인 4로 지정해두고, 가능한 방향을 체크한 뒤에 배열에 먼저 넣어주었다.

 

그 뒤엔 거울을 만난다면, 현재 진행 방향이 좌우라면 상하로 바꾸어서 나아가게끔하고, 그 반대라면 반대의 경우를 설정하고

거울을 세울 수 있는 위치에 거울을 세우지 않고 그냥 진행되게 할 수도 있기 때문에 이와 같은 경우도 추가해주었다.

 

코드에 부분마다 주석을 달아두었다.좀 더 짧게 코드를 짤 수 있을 것 같긴한데, 길게 풀어놓은 코드가 이해는 더 쉽지 않을까 해서 첨부한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	static char[][] map;
	static boolean[][][] visit;
	static int N;
	
	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());
        
        map = new char[N][N];
        visit = new boolean[N][N][4];
        int startX = 0, startY = 0;
        
        for (int i = 0; i < N; i++) {
        	String temp = br.readLine();
        	for (int j = 0; j < temp.length(); j++) {
        		map[i][j] = temp.charAt(j);
        		if (map[i][j] == '#') {
        			startX = i;
        			startY = j;
        		}
        	}
        }
        map[startX][startY] = '.'; 
        bfs(startX, startY);
        
    }
    
    static void bfs(int startX, int startY) {
    	PriorityQueue<Node> q = new PriorityQueue<>();
    	q.offer(new Node(startX, startY, 4, 0));
    	for (int i = 0; i < 4; i++) {
    		// 시작점 모든 방향으로 방문완료 처리
    		visit[startX][startY][i] = true;
    	}
    	
    	while (!q.isEmpty()) {
    		Node node = q.poll();
    		
    		// 목적지를 만나면 값 출력 후 종료
    		if (map[node.x][node.y] == '#') {
    			System.out.println(node.cnt);
    			return;
    		}
    		
    		if (node.dir == 4) {
    			// 시작점에서 갈 수 있는 방향 찾기
    			for (int i = 0; i < 4; i++) {
    				int newX = node.x + dx[i];
    				int newY = node.y + dy[i];
    				
    				if (!checkRange(newX, newY)) continue;
    				
    				if (map[newX][newY] != '*') {
    					q.offer(new Node(newX, newY, i, node.cnt));
    					visit[newX][newY][i] = true;
    				}
    			}
    		// 시작점이 아닌 경우
    		} else {
    			if (map[node.x][node.y] == '!') {
    				if (node.dir == 0 || node.dir == 1) { // 좌우로 움직이는 중이면
    					for (int i = 2; i < 4; i++) {
    						// 거울을 세워 위 아래로 움직이는 경우
    						int newX = node.x + dx[i];
    						int newY = node.y + dy[i];
    						
    						if (!checkRange(newX, newY)) continue;
    						
    						if (map[newX][newY] != '*' && !visit[newX][newY][i]) {
    							q.offer(new Node(newX, newY, i, node.cnt + 1));
    							visit[newX][newY][i] = true;
    						}
    					}
    				}
    				
    				if (node.dir == 2 || node.dir == 3) { // 위 아래로 움직이는 중이면
    					for (int i = 0; i < 2; i++) {
    						// 거울을 세워 좌우로 움직이는 경우
    						int newX = node.x + dx[i];
    						int newY = node.y + dy[i];
	    						
    						if (!checkRange(newX, newY)) continue;
    						
    						if (map[newX][newY] != '*' && !visit[newX][newY][i]) {
    							q.offer(new Node(newX, newY, i, node.cnt + 1));
    							visit[newX][newY][i] = true;
    						}
    					}
    				}			
    			}
    			
    			// 거울을 세우지 않고 진행되는 경우
				int newX = node.x + dx[node.dir];
				int newY = node.y + dy[node.dir];
				if (!checkRange(newX, newY)) continue;
				
				if (map[newX][newY] != '*' && !visit[newX][newY][node.dir]) {
					q.offer(new Node(newX, newY, node.dir, node.cnt));
					visit[newX][newY][node.dir] = true;
				}
    		}
    	}
    }
    
    static boolean checkRange(int x, int y) {
    	return x >= 0 && y >= 0 && x < N && y < N;
    }
}

class Node implements Comparable<Node>{
	int x;
	int y;
	int dir;
	int 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) {
		// TODO Auto-generated method stub
		return cnt - o.cnt;
	}
}