거울 설치 [백준 2151][JAVA][골드5][시뮬레이션][BFS][DP]

 

[광고 누르면 오늘의 행운 상승!!]

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

2151번: 거울 설치

BFS 시뮬레이션 DP 문제

맵이 최대 50X50 이므로 거울이 48! 개 있을 수 있다. 
-> 메모리와 시간초과에 주의할 것.

1. 출발지와 도착지를 Q에 담고 도착지를 꺼내어 '&'로 만든다
(둘 중 어느 곳에서 시작해도 같기 때문)

2. 출발지를 꺼내어 북동남서 순으로 Q에 집어넣고 BFS를 시작한다.

3. 기본적으로 자신이 갖고있는 방향(dir)으로 이동하는데 !을 만나면
왼쪽, 오른쪽을 추가적으로 큐에 삽입한다.

4. DP배열에 내가 가고있는 방향과 거울의 수를 저장하여
같은방향의 같은 거울의 수를 가진 요소들을 제거한다.(중복이동 방지)

5. &에 도달하게 되면 결과를 출력한다.

package Study0319;

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

class Mirror {
	int row, col, dir, mircnt;

	Mirror(int row, int col, int dir, int mircnt) {
		this.row = row;
		this.col = col;
		this.dir = dir;
		this.mircnt = mircnt;
	}
}

public class 거울설치 {

	public static final int[] dx = { 1, 0, -1, 0 };
	public static final int[] dy = { 0, 1, 0, -1 };
	public static int N, M, ans = Integer.MAX_VALUE;
	public static char[][] map;
	public static Queue<Mirror> q;
	public static int dp[][][];

	public static void main(String[] args) throws Exception {
//		System.setIn(new FileInputStream("test.txt"));
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();

		map = new char[N][N];
		q = new LinkedList<>();
		dp = new int[N][N][4];

		for (int i = 0; i < N; i++) {
			char[] ch = sc.next().toCharArray();
			for (int j = 0; j < N; j++) {
				for (int k = 0; k < 4; k++) {
					dp[i][j][k] = Integer.MAX_VALUE;
				}
				map[i][j] = ch[j];
				if (map[i][j] == '#')
					q.add(new Mirror(i, j, 0, 0));
			}
		}

		Mirror mi = q.poll();
		map[mi.row][mi.col] = '&';

		bfs();
		System.out.println(ans);
	}

	private static void bfs() {

		Mirror mi = q.poll();
		for (int i = 0; i < 4; i++) {
			q.add(new Mirror(mi.row, mi.col, i, 0));
		}

		while (!q.isEmpty()) {
			Mirror m = q.poll();

         if(dp[m.row][m.col][m.dir] < m.mircnt) continue;
         dp[m.row][m.col][m.dir] = m.mircnt;

			if (map[m.row][m.col] == '&') {
				ans = Math.min(ans, m.mircnt);
				continue;
			}

			//거울을 만나면 왼쪽 오른쪽 추가
	         if(map[m.row][m.col] == '!') {
	            q.add(new Mirror(m.row,m.col,(m.dir+3)%4,m.mircnt+1));
	            q.add(new Mirror(m.row,m.col,(m.dir+1)%4,m.mircnt+1));
	         }

			int nx = m.row + dx[m.dir];
			int ny = m.col + dy[m.dir];
			if (check(nx, ny) || map[nx][ny] == '*')
				continue;

			// 가던 방향 추가
			q.add(new Mirror(nx, ny, m.dir, m.mircnt));
		}
	}

	private static boolean check(int nx, int ny) {
		return nx < 0 || nx >= N || ny < 0 || ny >= N;
	}

}