[백준] 2151 거울 설치

거울 설치문제는 BFS를 이용해서 다음 경로를 탐색하고 메모이제이션을 이용해서 최소한의 횟수로 이동할 수 있는 지점을 제한합니다.

이동방향은 거울을 설치하는 경우 두가지와 거울을 설치하지 않는 경우 한기지로 선택합니다.

예를 들어 오른쪽으로 이동하는 경우 거울을 설치하면 위, 아래로 이동하고,

거울을 설치 하지 않는경우 오른쪽으로 계속 이동하게 됩니다.

모든 경우를 계산하여 도착지점 문의 메모이제이션의 값이 최소 이동 횟수가 됩니다.

	package sdk.backjun;
	import java.util.LinkedList;
	import java.util.Queue;
	import java.util.Scanner;
	/**
	* 백준, 2151
	* 거울설치
	*
	* @author whitebeard-k
	*
	*/
	public class Problem2151 {
	public static final int UP = 1;
	public static final int RIGHT = 2;
	public static final int DOWN = 3;
	public static final int LEFT = 4;
	public static int MIRROR = '!';
	public static int WALL = '*';
	public static int DOOR = '#';
	public static int N;
	public static int[][] map;
	public static int[][] memo;
	public static int startX;
	public static int startY;
	public static int endX;
	public static int endY;
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	N = sc.nextInt();
	sc.nextLine();
	boolean door = true;
	map = new int[N][N];
	memo = new int[N][N];
	for (int x = 0; x < N; x++) {
	String line = sc.nextLine();
	char[] chars = line.toCharArray();
	for (int y = 0; y < N; y++) {
	map[x][y] = chars[y];
	memo[x][y] = Integer.MAX_VALUE;
	// 문을 시작위치, 종료위치로 각각 입력
	if (map[x][y] == DOOR) {
	if (door) {
	startX = x;
	startY = y;
	door = false;
	} else {
	endX = x;
	endY = y;
	}
	}
	}
	}
	sc.close();
	// 상하좌우 모두로 이동
	Queue<Location> queue = new LinkedList<>();
	queue.add(new Location(UP, 0, startX, startY));
	queue.add(new Location(RIGHT, 0, startX, startY));
	queue.add(new Location(DOWN, 0, startX, startY));
	queue.add(new Location(LEFT, 0, startX, startY));
	bfs(queue);
	System.out.println(memo[endX][endY]);
	}
	public static void bfs(Queue<Location> queue) {
	while (!queue.isEmpty()) {
	Location current = queue.poll();
	// 방향에 따라 이동가능한 위치 선택
	switch (current.direction) {
	case UP:
	left(queue, current, 1);
	up(queue, current, 0);
	right(queue, current, 1);
	break;
	case RIGHT:
	up(queue, current, 1);
	right(queue, current, 0);
	down(queue, current, 1);
	break;
	case DOWN:
	left(queue, current, 1);
	down(queue, current, 0);
	right(queue, current, 1);
	break;
	case LEFT:
	up(queue, current, 1);
	left(queue, current, 0);
	down(queue, current, 1);
	break;
	}
	}
	}
	private static void down(Queue<Location> queue, Location current, int count) {
	int currentX = current.x;
	int nextY = current.y;
	int nextCount = current.count + count;
	for (int nextX = currentX + 1; nextX < N; nextX++) {
	if (map[nextX][nextY] == WALL)
	return;
	if (isMoveable(nextX, nextY, nextCount)) {
	queue.add(new Location(DOWN, nextCount, nextX, nextY));
	memo[nextX][nextY] = nextCount;
	}
	}
	}
	private static void right(Queue<Location> queue, Location current, int count) {
	int nextX = current.x;
	int currentY = current.y;
	int nextCount = current.count + count;
	for (int nextY = currentY + 1; nextY < N; nextY++) {
	if (map[nextX][nextY] == WALL)
	return;
	if (isMoveable(nextX, nextY, nextCount)) {
	queue.add(new Location(RIGHT, nextCount, nextX, nextY));
	memo[nextX][nextY] = nextCount;
	}
	}
	}
	private static void up(Queue<Location> queue, Location current, int count) {
	int currentX = current.x;
	int nextY = current.y;
	int nextCount = current.count + count;
	for (int nextX = currentX - 1; 0 <= nextX; nextX--) {
	if (map[nextX][nextY] == WALL)
	return;
	if (isMoveable(nextX, nextY, nextCount)) {
	queue.add(new Location(UP, nextCount, nextX, nextY));
	memo[nextX][nextY] = nextCount;
	}
	}
	}
	private static void left(Queue<Location> queue, Location current, int count) {
	int nextX = current.x;
	int currentY = current.y;
	int nextCount = current.count + count;
	for (int nextY = currentY - 1; 0 <= nextY; nextY--) {
	if (map[nextX][nextY] == WALL)
	return;
	if (isMoveable(nextX, nextY, nextCount)) {
	queue.add(new Location(LEFT, nextCount, nextX, nextY));
	memo[nextX][nextY] = nextCount;
	}
	}
	}
	private static boolean isMoveable(int nextX, int nextY, int nextCount) {
	if (map[nextX][nextY] == MIRROR && nextCount < memo[nextX][nextY] || (map[nextX][nextY] == DOOR && nextX == endX && nextY == endY) && nextCount < memo[nextX][nextY]) {
	return true;
	}
	return false;
	}
	}
	class Location {
	public int direction;
	public int count;
	public int x;
	public int y;
	public Location(int direction, int count, int x, int y) {
	super();
	this.direction = direction;
	this.count = count;
	this.x = x;
	this.y = y;
	}
	}

view raw Problem2151.java hosted with ❤ by GitHub