[백준] 2515 거울설치

문제

---

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

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

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

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

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

 

 

풀이

---

우선 나는 N x N 배열에 모든 방향(4개방향)에 따라 최소 값을 저장하는 방식으로 접근을 했다.

빛의 방향이 꺾일 수 있는 곳은 '!' 부분에서만 가능하기 때문에 이럴 때는 방향을 바꿔주고 값을 +1 해줬다.

 

그리고 거울의 최소를 먼저 확인하기 위해 우선순위 큐(Priority Queue)를 사용하였다.

BFS 와 다익스트라 알고리즘을 섞어서 풀었지만, 시간이 오래걸려서 다른 풀이도 찾아 보았다.

 

<내가 푼 풀이>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	static char[][] map;
	static int[][][] dir;
	static int n;
	static point start, end;
	static int answer;
	static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = parseInt(br.readLine());
		
		map = new char[n][];
		dir = new int[n][n][4];
		for(int i = 0 ; i < n ; i++) {
			map[i] = br.readLine().toCharArray();
			for(int  j = 0 ; j < n ; j++) {
				if(map[i][j] == '#') {
					if(start == null) {
						start = new point(i, j, 0, 0);
					}
					else {
						end = new point(i, j, 0, 0);
					}
				}
				
				for(int k = 0 ; k < 4;  k++) {
					dir[i][j][k] = -1;
				}
			}
		}
		
		answer = Integer.MAX_VALUE;
		bfs();
		
		System.out.println(answer);
	}
	
	static void bfs() {
		
		PriorityQueue<point> queue = new PriorityQueue<>();
		for(int i = 0 ; i < 4; i++) {
			int nx = start.x + direction[i][0];
			int ny = start.y + direction[i][1];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= n) { continue;}
			if(map[nx][ny] == '*') {continue;}
			
			dir[nx][ny][i] = 0;
			queue.add(new point(nx, ny, i, 0));
		}
		
		while(!queue.isEmpty()) {
			point top = queue.poll();
			
			if(end.x == top.x && end.y == top.y) {
				answer = Math.min(answer, top.w);
				continue;
			}
			
			// ! 면 거울 둘 수 있으니 꺽이는 방향 고려
			if(map[top.x][top.y] == '!') {				
				if(top.d < 2) {
					for(int i = 2 ; i < 4 ; i++) {
						int nx = top.x + direction[i][0];
						int ny = top.y + direction[i][1];

						if(nx < 0 || nx >= n || ny < 0 || ny >= n ) {continue;}
						if(map[nx][ny] == '*' || (dir[nx][ny][i] != -1 && dir[nx][ny][i] < top.w + 1)){ continue;}
						
						dir[nx][ny][i] = top.w + 1;
						queue.add(new point(nx, ny, i, top.w + 1));
					}
				}
				else{
					for(int i = 0 ; i < 2 ; i++) {
						int nx = top.x + direction[i][0];
						int ny = top.y + direction[i][1];

						if(nx < 0 || nx >= n || ny < 0 || ny >= n ) {continue;}
						if(map[nx][ny] == '*' || (dir[nx][ny][i] != -1 && dir[nx][ny][i] < top.w + 1)) { continue;}
						
						dir[nx][ny][i] = top.w + 1;
						queue.add(new point(nx, ny, i, top.w + 1));
					}
				}
			}
			
			// 빛이 직진 하는 경우
			int nx = top.x + direction[top.d][0];
			int ny = top.y + direction[top.d][1];
			
			if(nx < 0 || nx >= n || ny < 0 || ny >= n ) { continue;}
			if(map[nx][ny] == '*' || (dir[nx][ny][top.d] != -1 && dir[nx][ny][top.d] < top.w))  { continue; }
			
			dir[nx][ny][top.d] = top.w;
			queue.add(new point(nx, ny, top.d, top.w));
		}
		
	}
	
	static class point implements Comparable<point>{
		int x, y, d, w;
		point(int x, int y, int d, int w){
			this.x = x;
			this.y = y;
			this.d = d;
			this.w = w;
		}
		@Override
		public int compareTo(point o) {
			// TODO Auto-generated method stub
			return this.w - o.w;
		}
	}
}

 

 

 

풀이를 찾아보니 4가지 방향에 따라서 찾는것은 맞다.

하지만 다른점은 나는 '.' 의 경우에도 Queue 넣어서 정렬을 하면서 시간이 더 많이 걸린것으로 보인다.

아래에 있는 코드는 빈칸의 경우에는 Queue에 넣지 않고 거울의 개수만 초기화 해준다.

<여러 풀이를 보고 정리한 코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
	
	static char[][] map;
	static int[][][] dir;
	static int n;
	static point start, end;
	static int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
	static int answer;
	static StringBuilder sb = new StringBuilder();

	public static int parseInt(String string) {
		return Integer.parseInt(string);
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		n = parseInt(br.readLine());
		
		map = new char[n][];
		dir = new int[n][n][4];
		for(int i = 0 ; i < n ; i++) {
			map[i] = br.readLine().toCharArray();
			for(int  j = 0 ; j < n ; j++) {
				if(map[i][j] == '#') {
					if(start == null) {
						start = new point(i, j, -1);
					}
					else {
						end = new point(i, j, -1);
					}
				}
				
				for(int k = 0 ; k < 4;  k++) {
					dir[i][j][k] = -1;
				}
			}
		}
		
		answer = Integer.MAX_VALUE;
		bfs();
		
		System.out.println(answer);
	}
	
	static boolean isPossible(int x, int y, int d) {
		return x < 0 || x >= n || y < 0 || y >= n ||
				map[x][y] == '*' || dir[x][y][d] != -1 ? false : true;
	}
	
	static void bfs() {
		
		Queue<point> queue = new LinkedList<>();
		queue.add(start);
		
		for(int i = 0 ; i < 4; i++) {
			dir[start.x][start.y][i] = 0; 
		}
		
		while(!queue.isEmpty()) {
			point top = queue.poll();
			
			for(int i = 0 ; i < 4 ; i++) {
				int nx = top.x + direction[i][0];
				int ny = top.y + direction[i][1];
				
				if(!isPossible(nx, ny, i)) continue;
				
				int mirror = 0;
				if(top.d == -1) {
					mirror = 0;
				}
				else {
					if(top.d == i) 
						mirror = dir[top.x][top.y][top.d];
					else
						mirror = dir[top.x][top.y][top.d] + 1; 
				}
				
				
				while(isPossible(nx, ny, i)) {
					dir[nx][ny][i] = mirror;
					
					if(map[nx][ny] == '!') { queue.offer(new point(nx, ny, i)); }
					
					nx += direction[i][0];
					ny += direction[i][1];
				}
			}
		}
		
		for(int i = 0 ; i < 4 ; i++) {
			if(dir[end.x][end.y][i] != -1 ) {
				answer = Math.min(answer, dir[end.x][end.y][i]);
			}
		}
	}
	
	static class point{
		int x, y, d;
		point(int x, int y, int d){
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
}