백준 13459 - (Java) 구슬 탈출

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

13459번: 구슬 탈출

1. 유형

구현, dfs

 

2. 문제 접근

 

2-1. 설계

2-2. 설명

먼저 dfs를 사용했습니다.

제한 조건에 구슬 이동을 총 10번만 한다고 했으므로, 모든 경우의 수를 따져보면 4^10입니다. 백만 정도밖에

되지 않기 때문에 모든 경우의 수를 따져봤습니다.

 

위에 설계도처럼 이동하다가 주의할 점은 red와 blue가 겹치는 경우입니다.

그림 1

그럼 위의 경우 어떻게 해야 할까요?

원래대로 라면 "그림 2"처럼 나와야 합니다. 

처음 좌표를 비교해서 해결 가능합니다.

왼쪽으로 기울였을 때, 블루의 col이 더 작습니다. 그렇다면 원래 더 왼쪽에 있었다는 의미니깐,

red의 col을 +1 해주면 끝.

위 과정을 동서남북 모두 따로따로 진행해주면 예외 없이 처리 가능합니다.

 

그림 2

3. 코드

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

public class Main {
	static int N, M, ans = 0;
	static char[][] map;
	static int d[][] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		map = new char[N][M];
		int r = 0, c = 0, r2 = 0, c2 = 0;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			map[i] = st.nextToken().toCharArray();
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 'R') {
					r = i;
					c = j;
					map[i][j]='.';
				} else if (map[i][j] == 'B') {
					r2 = i;
					c2 = j;
					map[i][j]='.';
				}
			}
		}
		dfs(0, r, c, r2, c2);
		System.out.println(ans);
	}

	static void dfs(int dep, int r, int c, int r2, int c2) {
		if (ans == 1)
			return;
		if (dep == 10) {
			return;
		}
		for (int k = 0; k < 4; k++) {
			int red[] = { r, c };
			int blue[] = { r2, c2 };
			move(red, k);
			move(blue, k);
			int type = check(red, blue);//0: 실패, 1: 성공, 2: 빈칸
			if (type == 0) {
				continue;
			} else if (type == 1) {
				// 정답
				ans = 1;
				return;
			} else {
				if (red[0] == blue[0] && red[1] == blue[1]) {
					if (k == 0) {// 상
						if (r < r2) {// 처음 레드가 더 위에 있음
							blue[0] += 1;
						} else {
							red[0] +=1;
						}
					}else if(k==2) {
						if (r > r2) {
							blue[0] -= 1;
						} else {
							red[0] -=1;
						}
					}else if(k==1) {
						if (c > c2) {
							blue[1] -= 1;
						} else {
							red[1] -=1;
						}
					}
					else if(k==3){// 좌
						if (c < c2) {
							blue[1] += 1;
						} else
							red[1] += 1;
					}
				}
			}
			dfs(dep + 1, red[0], red[1], blue[0], blue[1]);
		}
	}

	static int check(int red[], int blue[]) {
		int r = red[0], c = red[1], r2 = blue[0], c2 = blue[1];
		if (map[r][c] == 'O' && map[r2][c2] == 'O') {
			return 0;
		}
		if (map[r][c] == 'O' && map[r2][c2] != 'O') {
			return 1;
		}
		if (map[r][c] != 'O' && map[r2][c2] == 'O') {
			return 0;
		}
		if (map[r][c] != 'O' && map[r2][c2] != 'O') {
			return 2;
		}
		return 0;
	}

	static void move(int pair[], int k) {
		int r = pair[0], c = pair[1];
		while (true) {
			r+=d[k][0];
			c+=d[k][1];
			if (map[r][c] == '#') {
				r-=d[k][0];
				c-=d[k][1];
				break;
			} else if (map[r][c] == 'O') {
				break;
			}
		}
		pair[0] = r;
		pair[1] = c;
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}