JUST WRITE IT. HomeArchivesTagsCategories
백준 13460번 구슬 탈출 2
|AlgorithmBOJ|

#13460. 구슬 탈출 2

Problem

Solution

  • 시뮬레이션 문제이다.
  • 어떤 방향으로 기울일지 정해야 한다. (모든 경우를 구해야 한다. - 재귀 사용)
    이전 방향과 반대되는 방향으로 이동할 필요는 없다.
  • 맵을 갱신할 필요는 없고 구슬의 위치만 변경하면 된다.
  • 각 경우마다 구슬의 위치를 다음 작업에 넘겨주어야 한다. (재귀 함수 인자로 넘기기)
  • 기울이기 재귀함수
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    Move(이동 횟수, 이전 방향, 빨간 구슬 위치, 파란 구슬 위치)
     if 이동 횟수 > 10  return
     if 파란 구슬이 구멍에 들어간 경우 return
     if 빨간 구슬만 구멍에 들어간 경우 최솟값 갱신 return
     4 방향 이동
      벽이 아닐 때까지, 구멍 일 때까지 이동
      // 빨간 구슬 이동
      // 파란 구슬 이동
      이동이 끝나면
      if 위치가 겹칠 때
         if 구멍이면 Move(이동 횟수 + 1, 방향, 위치)
         else 
            같은 행일 때
    				같은 열일 때
    				위치 이동
            Move(이동횟수 +1, 방향, 위치)
      else
    		 Move(이동횟수 +1, 방향, 위치)
    빨간 구슬이 방향에 맞게 이동하고, 그 후 파란 구슬이 이동한다.

구멍에 들어갔거나 같은 행이거나 같은 열이면 위치가 같게 된다. 이때 방향과 처음 위치에 맞게 방향을 바꿔준다.

갱신이 끝났으면 재귀함수를 호출해준다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
using namespace std;
int N, M, ans = 1e9;
int g_x, g_y;
char board[11][11];
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
int count_dir[4] = { 1, 0, 3, 2 };
struct Red {
	int x, y;
};
struct Blue {
	int x, y;
};
void Move(int cnt, int prior_dir, Red r, Blue b) {
	if (cnt > 10) return;
	if (b.x == g_x && b.y == g_y) return; // 파란 구슬 구멍 통과
	if (r.x == g_x && r.y == g_y) { // 빨간 구슬만 구멍 통과
		if (ans > cnt) ans = cnt;
		return;
	}
	for (int dir = 0; dir < 4; ++dir) {
		Red nr = { r.x, r.y }; Blue nb = { b.x, b.y }; // next
		if (prior_dir != -1 && count_dir[prior_dir] == dir) continue;
		while (true) {
			if (board[nr.x + dx[dir]][nr.y + dy[dir]] == '#') break;
			nr.x += dx[dir];
			nr.y += dy[dir];
			if (board[nr.x][nr.y] == 'O') break;
		}
		while (true) {
			if (board[nb.x + dx[dir]][nb.y + dy[dir]] == '#') break;
			nb.x += dx[dir];
			nb.y += dy[dir];
			if (board[nb.x][nb.y] == 'O') break;
		}
		if (nr.x == nb.x && nr.y == nb.y) { // 겹칠 때
			if (board[nr.x][nr.y] == 'O') Move(cnt + 1, dir, nr, nb);
			else {
				if (r.x == b.x) { // 같은 행
					if (r.y < b.y) { // R B
						if (dir == 2) nb.y++;
						else if (dir == 3) nr.y--;
					}
					else { // B R
						if (dir == 2) nr.y++;
						else if (dir == 3) nb.y--;
					}
				}
				else if (r.y == b.y) { // 같은 열
					if (r.x < b.x) { // R이 B보다 위
						if (dir == 0) nb.x++;
						else if (dir == 1) nr.x--;
					}
					else { // R이 B보다 아래
						if (dir == 0) nr.x++;
						else if (dir == 1) nb.x--;
					}
				}
				Move(cnt + 1, dir, nr, nb);
			}
		}
		else {
			Move(cnt + 1, dir, nr, nb);
		}
	}
}
int main() {
	cin >> N >> M;
	Red r; Blue b;
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < M; ++j) {
			cin >> board[i][j];
			if (board[i][j] == 'O') {
				g_x = i; g_y = j;
			}  
			else if (board[i][j] == 'R') {
				r.x = i; r.y = j;
			}
			else if (board[i][j] == 'B') {
				b.x = i; b.y = j;
			}
		}
	}
	Move(0, -1, r, b);
	if (ans == 1e9) cout << -1 << "\n";
	else cout << ans << "\n";
	return 0;
}

문제 풀고나서 찾아본 깔끔한 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<cstdio>
int n, m;
int rx, ry, bx, by;
char a[11][11];
int ans = 11;
void go(int rx, int ry, int bx, int by, int mx, int my, int cnt){
	if (cnt >= ans) return;
	int rm = 0, bm = 0;
	if (mx != my){
		while (a[bx + mx][by + my] - '#'){
			bx += mx;
			by += my;
			bm++;
			if (!(a[bx][by] - 'O'))
				return;
		}
		while (a[rx + mx][ry + my] - '#'){
			rx += mx;
			ry += my;
			rm++;
			if (!(a[rx][ry] - 'O')){
				ans = ans < cnt ? ans : cnt;
				return;
			}
		}
	}
	if (rx == bx && ry == by)
		if (rm < bm)
			bx -= mx, by -= my;
		else
			rx -= mx, ry -= my;
	if (mx == 0){
		go(rx, ry, bx, by, 1, 0, cnt + 1);
		go(rx, ry, bx, by, -1, 0, cnt + 1);
	}
	if (my == 0){
		go(rx, ry, bx, by, 0, 1, cnt + 1);
		go(rx, ry, bx, by, 0, -1, cnt + 1);
	}
}
int main(){
	scanf("%d %d", &n, &m);
	for (int i = 0; i < n; i++)
		scanf("%s", a[i]);
	for (int i = 1; i < n - 1; i++){
		for (int j = 1; j < m - 1; j++){
			if (a[i][j] == 'R')
				rx = i, ry = j;
			if (a[i][j] == 'B')
				bx = i, by = j;
		}
	}
	go(rx, ry, bx, by, 0, 0, 0);
	printf("%d", ans < 11 ? ans : -1);
}
Algorithm