[백준] 구슬 탈출2 (문제번호 : 13460)

오랜만에 다시 시작한 알고리즘

그래서 쉬운거, 구현 위주로 일단 시작해보려 한다.

 

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

 

13460번: 구슬 탈출 2

모든 알고리즘이 그렇듯이 문제의 제약이나 조건을 먼저 살피는 것이 중요하다

문제에서 보여주는 힌트나 반례가 될 수 있는 케이스를 찾는 것도 알고리즘 해결에 필수적인 능력이다.

 

먼저 복잡도를 생각해보기 위한 조건은 아래 정도로 보인다.

문제에서 추출한 조건 1. 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다  -> N과 M은 최대 같으므로 그냥 N으로 퉁친다 2. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.  -> 구슬을 한번 굴릴 때 각 구슬이 최대 N개의 칸을 거쳐야 하므로 O(2 * N)  3. 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.  -> 한 케이스에서 나올 수 있는 가지 수가 4개, 전체 탐색으로 생각 했을 때 O(4^N)  -> 전체 굴릴때를 생각해보면 O(2 * N * 4^N) 4. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.  -> 10번 이하이므로 가지의 depth가 10 이하로 나옴 2 * 10 * 4^10 = 약 20,000,000 번..

대충 1억번의 연산이 1초라고 가정해보면 제한시간 2초 안에 충분히 들어올 수 있다.

적절한 가지치기와 제약을 준다면ㅎㅎ

 

전형적인 Brute Force 문제이고 범위가 작아서 전체 탐색을 위한 DFS, BFS 로 다 풀기 가능하다.

좀 더 직관적이고 구현이 쉬운 DFS로 접근해본다.

나중에 BFS 버전도 올려야지

 

뭔가 케이스 처리를 막 하다 보니까 코드가 더러워진 느낌..

 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
	public static final int[] dx = { 0, 0, 1, -1 }; // 동서남북
	public static final int[] dy = { 1, -1, 0, 0 };

	public static final int EAST = 0;
	public static final int WEST = 1;
	public static final int SOUTH = 2;
	public static final int NORTH = 3;

	public static final char RED = 'R';
	public static final char BLUE = 'B';
	public static final char HOLE = 'O';
	public static final char WALL = '#';
	public static final char ROAD = '.';

	public static final int FAIL = -1;
	public static final int LIMIT = 10;
	public static final int MAX = 999;

	public static char[][] map;
	public static boolean[][][][] visited;

	public static int N;
	public static int M;

	public static int result;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		result = MAX;
		map = new char[N][M];
		visited = new boolean[N][M][N][M];
		Ball now = new Ball();
		for (int i = 0; i < N; i++) {
			String line = br.readLine();
			for (int j = 0; j < M; j++) {
				char here = line.charAt(j);
				if (here == BLUE) {
					now.bx = i;
					now.by = j;
				} else if (here == RED) {
					now.rx = i;
					now.ry = j;
				} else {
					map[i][j] = here;
				}
			}
		}
		visited[now.rx][now.ry][now.bx][now.by] = true;
		move(now, 1, -1);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(String.valueOf(result == MAX ? -1 : result));
		bw.flush();
		bw.close();

	}

	public static void move(Ball now, int cnt, int dir) {

		if (cnt > LIMIT) {
			return;
		}

		for (int i = 0; i < 4; i++) {
			if (isSameDirection(i, dir)) continue;
			Ball next = new Ball();
			int bx = now.bx;
			int by = now.by;
			int rx = now.rx;
			int ry = now.ry;
			int bcnt = 0;
			int rcnt = 0;
			// 파란볼 먼저 이동
			while (map[bx + dx[i]][by + dy[i]] != WALL) {
				bx += dx[i];
				by += dy[i];
				bcnt++;
				if (map[bx][by] == HOLE)
					break; // 구녕 들어가면 끝
			}
			next.bx = bx;
			next.by = by;
			// 빨간볼 이동
			while (map[rx + dx[i]][ry + dy[i]] != WALL) {
				rx += dx[i];
				ry += dy[i];
				rcnt++;
				if (map[rx][ry] == HOLE)
					break;
			}
			next.rx = rx;
			next.ry = ry;

			// 파란볼이 구녕이면 이 판은 끗
			if (map[next.bx][next.by] == HOLE)
				continue;

			// 빨간볼이 구녕이면 cnt 리턴
			if (map[next.rx][next.ry] == HOLE) {
				result = Math.min(cnt, result);
				break;
			}
			// 둘 다 그자리면 이 이상 안감
			if(now.rx == next.rx && now.ry == next.ry && now.bx == next.bx && now.by == next.by) continue;
			
			// 같은 칸이면 많이 움직인 구슬을 이전 칸으로 이동
			if (next.bx == next.rx && next.by == next.ry) {
				if (bcnt > rcnt) {
					next.bx -= dx[i];
					next.by -= dy[i];
				} else {
					next.rx -= dx[i];
					next.ry -= dy[i];
				}
			}
			// 방문 했으면 안감
			if (visited[next.rx][next.ry][next.bx][next.by]) continue;

			visited[next.rx][next.ry][next.bx][next.by] = true;
			move(next, cnt + 1, i);
			visited[next.rx][next.ry][next.bx][next.by] = false;
		}
	}
	private static boolean isSameDirection(int now, int before) {
		if (before == now) return true;
		else {
			switch (before) {
				case EAST:
					if(now==WEST) return true;
					break;
				case WEST:
					if(now==EAST) return true;
					break;
				case SOUTH:
					if(now==NORTH) return true;
					break;
				case NORTH:
					if(now==SOUTH) return true;
					break;
				default:
					return false;
			}
		}
		return false;
	}
}

class Ball {
	int rx;
	int ry;
	int bx;
	int by;

	public Ball(int rx, int ry, int bx, int by) {
		this.rx = rx;
		this.ry = ry;
		this.bx = bx;
		this.by = by;
	}

	public Ball() {
	}
}