알고리즘 스터디 8월 2주차 문제1 (구슬 탈출2)

문제#

  • 링크로 대체

풀이 및 주저리..

오랜만에 풀어본 삼성역량테스트 기출문제중 하나이다. 얼핏보면 간단하게 BFS로만 풀 수 있을 것 같지만.. 전혀 그렇지 않았다. 생각해야할 상황들이 좀 많고 고려해야할 변수들도 많았다.

쓰다보니 좀 많이 지저분해졌지만.. 결국 두시간정도 걸려서 문제를 풀게 되었다. 머리속에서 많이 놓쳤던 부분은 바로 구슬이 함께 움직인다는 것. 즉, 구슬 두개가 특정한 상황에서 어떤 구슬을 먼저 움직여줘야하는지 결정해줘야하는 부분이였던 것 같다. 그리고 두개의 구슬이 같은 위치에 있을때의 방문처리. 이 두 개가 가장 핵심이였던 것 같다.

코드

package baekjoon.algorithm.simulation;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Problem13460 {
	static int n, m, rX, rY, bX, bY;
	static char[][] map;
	static boolean[][][][] isVisited;
	static final int[] dx = { -1, 1, 0, 0 }, dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stk.nextToken());
		m = Integer.parseInt(stk.nextToken());
		map = new char[n][m];
		isVisited = new boolean[n][m][n][m];
		for (int r = 0; r < n; r++) {
			map[r] = br.readLine().toCharArray();
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'R') {
					rX = i;
					rY = j;
					map[i][j] = '.';
				}
				if (map[i][j] == 'B') {
					bX = i;
					bY = j;
					map[i][j] = '.';
				}
			}
		}
		System.out.println(getAnswer());

	}

	private static int getAnswer() {
		int answer = -1;
		Queue<int[]> queue = new LinkedList<int[]>();
		queue.add(new int[] { rX, rY });
		queue.add(new int[] { bX, bY });
		int level = 0;
		boolean isGameOver = false;
		A: while (!queue.isEmpty() && level < 10) {
			level++;
			int qSize = queue.size() / 2;
			for (int i = 0; i < qSize; i++) {
				int[] red = queue.poll();
				int[] blue = queue.poll();
				// 4 방향으로 기울이자
				for (int d = 0; d < 4; d++) {
					// 누구부터 움직여야할지 정해줘야한다.
					int[][] redBlue;
					if (d == 0 && red[1] == blue[1] && red[0] > blue[0]) {
						redBlue = moveRedBlue(red, blue, d, false);
					} else if (d == 1 && red[1] == blue[1] && red[0] < blue[0]) {
						redBlue = moveRedBlue(red, blue, d, false);
					} else if (d == 2 && red[0] == blue[0] && red[1] > blue[1]) {
						redBlue = moveRedBlue(red, blue, d, false);
					} else if (d == 3 && red[0] == blue[0] && red[1] < blue[1]) {
						redBlue = moveRedBlue(red, blue, d, false);
					} else {
						redBlue = moveRedBlue(red, blue, d, true);
					}
					if (redBlue[1][0] == 0 && redBlue[1][1] == 0)
						continue;
					else {
						if (redBlue[0][0] == 0 && redBlue[0][1] == 0) {
							isGameOver = true;
							break A;
						}
						if (isVisited[redBlue[0][0]][redBlue[0][1]][redBlue[1][0]][redBlue[1][1]])
							continue;
						isVisited[redBlue[0][0]][redBlue[0][1]][redBlue[1][0]][redBlue[1][1]] = true;
						queue.add(redBlue[0]);
						queue.add(redBlue[1]);
					}
				}
			}
		}
		return isGameOver ? level : answer;
	}

	private static int[][] moveRedBlue(int[] red, int[] blue, int dir, boolean isRedFirst) {
		int[][] redBlue = new int[2][2];
		if (isRedFirst) {
			red = move(red[0], red[1], dir);
			map[red[0]][red[1]] = 'R';
			blue = move(blue[0], blue[1], dir);
		} else {
			blue = move(blue[0], blue[1], dir);
			map[blue[0]][blue[1]] = 'B';
			red = move(red[0], red[1], dir);
		}
		map[red[0]][red[1]] = '.';
		map[blue[0]][blue[1]] = '.';
		redBlue[0] = red;
		redBlue[1] = blue;
		return redBlue;
	}

	private static int[] move(int x, int y, int d) {
		while (map[x + dx[d]][y + dy[d]] == '.') {
			x += dx[d];
			y += dy[d];
		}
		// 구멍에 들어간 경우
		if (map[x + dx[d]][y + dy[d]] == 'O')
			return new int[] { 0, 0 };
		return new int[] { x, y };
	}
}

기억에 남길 것!

  • 시뮬레이셔는 상황을 그리면서 생각해보자.
© 2020 JunhoBaik, Built with Gatsby