문제 링크
문제
채영이는 거울을 들여다보는 것을 참 좋아한다. 그래서 집 곳곳에 거울을 설치해두고 집 안을 돌아다닐 때마다 거울을 보곤 한다.
채영이는 새 해를 맞이하여 이사를 하게 되었는데, 거울을 좋아하는 그녀의 성격 때문에 새 집에도 거울을 매달만한 위치가 여러 곳 있다. 또한 채영이네 새 집에는 문이 두 개 있는데, 채영이는 거울을 잘 설치하여 장난을 치고 싶어졌다. 즉, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 거울을 설치하고 싶어졌다.
채영이네 집에 대한 정보가 주어졌을 때, 한 쪽 문에서 다른 쪽 문을 볼 수 있도록 하기 위해 설치해야 하는 거울의 최소 개수를 구하는 프로그램을 작성하시오.
거울을 설치할 때에는 45도 기울어진 대각선 방향으로 설치해야 한다. 또한 모든 거울은 양면 거울이기 때문에 양 쪽 모두에서 반사가 일어날 수 있다. 채영이는 거울을 매우 많이 가지고 있어서 거울이 부족한 경우는 없다고 하자.
거울을 어떻게 설치해도 한 쪽 문에서 다른 쪽 문을 볼 수 없는 경우는 주어지지 않는다.
입력
첫째 줄에 집의 크기 N (2 ≤ N ≤ 50)이 주어진다. 다음 N개의 줄에는 N개의 문자로 집에 대한 정보가 주어진다. ‘#’는 문이 설치된 곳으로 항상 두 곳이며, ‘.’은 아무 것도 없는 것으로 빛은 이 곳을 통과한다. ‘!’은 거울을 설치할 수 있는 위치를 나타내고, ‘*’은 빛이 통과할 수 없는 벽을 나타낸다.
출력
첫째 줄에 설치해야 할 거울의 최소 개수를 출력한다.
알고리즘: 다익스트라, BFS
풀이
이 문제는 도착지까지의 최소 거리가 아니다. 거울의 최소 개수를 출력하는 문제다. 그렇다면 어떻게 거울의 최소 개수를 찾을 수 있을까? 이때 다익스트라 알고리즘을 사용하면 된다.
먼저 빛의 이동 방향은 동서남북으로 총 4방향이다. 그렇기 때문에 최소 비용을 저장할 배열도 모든 방향의 최소 비용을 저장해야 한다. 즉 3차원 배열 visited[4(방향)][y좌표][x좌표]가 필요하다.
여기까지 문제를 풀었다면, 나머지는 문제의 나온데로 BFS를 이용해 탐색해주면 된다.
현재 좌표가 '.'인 경우 거울을 설치할 수 없다. 즉 이동 방향은 그대로다. 여기서 visited[방향][ny][nx]보다 mc(현재까지 카운트한 거울 개수)가 더 작다면 최소 비용을 갱신하는 탐색이기 때문에 탐색을 허용하고, 그게 아니라면 탐색을 진행하지 않는다.
현재 좌표가 '!'인 경우 거울을 설치할 수 있다. 거울은 45도 기울어진 대각선 방향으로만 설치할 수 있기 때문에 전에 이동 방향이 북,남이였다면 동서로 거울을 설치해서 이동할 수 있고, 동,서였다면 북남으로 거울을 설치해서 이동할 수 있다. 그러니까 총 3가지 방향으로 이동할 수 있다. (하나는 원래 진행 방향 거울 설치 x) 거울을 설치하는 경우 mc + 1을 해서 똑같이 최소 비용을 갱신하는 탐색만 허용하면 된다.
탐색이 종료되면 도착지로 설정한 문 좌표를 방향별로 비교해가면서 최솟값을 출력하면 된다.
-> 문은 두 개이기 때문에 하나는 출발지, 하나는 도착지로 미리 설정해야 한다.
소스 코드
import java.io.*;
import java.util.*;
class Node {
int x,y,c,dir;
Node(int x, int y, int c, int dir) {
this.x = x;
this.y = y;
this.c = c;
this.dir = dir;
}
}
class Point {
int x,y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static final int dx[] = {-1, 0, 1, 0};
static final int dy[] = {0, -1, 0 ,1};
static final int l_d[][] = {{0,1,3},{0,1,2},{1,2,3},{0,2,3}};
static int N;
static char house[][];
static int visited[][][];
static ArrayList<Point> door = new ArrayList<>();
static int ans = Integer.MAX_VALUE;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
house = new char[N][N];
visited = new int[4][N][N]; //0: 서, 1: 북, 2: 동, 3: 남
td_arr_fill(visited, Integer.MAX_VALUE);
for(int i=0; i<N; i++) {
String input = br.readLine();
for(int j=0; j<N; j++) {
house[i][j] = input.charAt(j);
if(house[i][j]=='#') door.add(new Point(j,i));
}
}
for(int i=0; i<4; i++) visited[i][door.get(0).y][door.get(0).x] = 0;
for(int i=0; i<4; i++) {
int nx = door.get(0).x + dx[i];
int ny = door.get(0).y + dy[i];
if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
if(house[ny][nx] != '*' && 0 < visited[i][ny][nx]) {
BFS(new Node(nx, ny, 0, i));
}
}
}
for(int i=0; i<4; i++) {
ans = Math.min(ans, visited[i][door.get(1).y][door.get(1).x]);
}
System.out.println(ans);
}
static void BFS(Node start) {
Queue<Node> que = new LinkedList<>();
que.add(start);
visited[start.dir][start.y][start.x] = 0;
while(que.size()!=0) {
Node n = que.poll();
if(house[n.y][n.x] == '.') {
//빛이 그냥 통과하는 곳
int nx = n.x + dx[n.dir];
int ny = n.y + dy[n.dir];
if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
if(house[ny][nx] != '*' && n.c < visited[n.dir][ny][nx]) {
que.add(new Node(nx, ny, n.c, n.dir));
visited[n.dir][ny][nx] = n.c;
}
}
} else if(house[n.y][n.x] == '!') {
//거울을 설치할 수 있는 곳
for(int i=0; i<l_d[n.dir].length; i++) {
int next_dir = l_d[n.dir][i];
int nx = n.x + dx[next_dir];
int ny = n.y + dy[next_dir];
if((nx>=0 && nx<=N-1) && (ny>=0 && ny<=N-1)) {
int n_mc = n.c;
if(n.dir != next_dir) n_mc += 1;
if(house[ny][nx] != '*' && n_mc < visited[next_dir][ny][nx]) {
que.add(new Node(nx, ny, n_mc, next_dir));
visited[next_dir][ny][nx] = n_mc;
}
}
}
}
}
}
static void td_arr_fill(int arr[][][], int value) {
for(int i=0; i<arr.length; i++) {
for(int j=0; j<arr[i].length; j++) {
Arrays.fill(arr[i][j], value);
}
}
}
}