구슬 탈출2

작성일 | In

[백준] 13460번 - 구슬 탈출2

문제 링크

요구사항을 정확히 코드로 옮기는 능력을 요구하는 시뮬레이션 문제이다.

난 이러한 문제를 풀 때 맵으로 주어지는 n,m의 최대 크기를 확인해보고, 이 크기가 작다면 브루트포스로 접근하는 편이다. 이 문제는 n,m이 10이하이므로 충분히 브루트포스로 풀이할 수 있다고 생각했다.
이 문제의 핵심은 크게 3가지로 구분할 수 있다.

  1. 구슬은 벽을 만나거나 다른 구슬을 만나거나, 구멍에 들어갈 때 까지 한 턴에 한 쪽 방향으로만 이동한다.
  2. 파란 구슬이 구멍에 들어가면 안된다.
  3. 두 구슬이 같은 행이나 열에 존재할 경우, 어떠한 구슬을 먼저 이동시키느냐가 이동 결과에 영향을 미칠 수 있다.
    예를 들어, 두 구슬이 같은 행에 위치하고 두 구슬 사이에 벽이 없으며, 빨간 구슬이 파란 구슬보다 오른쪽에 있을 때 보드를 오른쪽으로 기울이는 상황을 가정해보자. 코드에서 파란 구슬을 먼저 움직인다면 파란 구슬은 중간에 빨간 구슬에 막혀 멈추게 되고, 빨간 구슬은 벽을 만날 때 까지 오른쪽으로 움직인다. 하지만 이 결과는 잘못된 결과이며, 파란 구슬과 빨간 구슬은 오른쪽 벽에 나란히 붙어 있어야 한다. 이러한 상황을 방지하기 위해 두 구슬이 같은 열, 같은 행에 있을 때 움직이는 방향에 따라 어떤 구슬을 먼저 움직일지 분기점을 나누어 주어야 한다.


이 핵심을 바탕으로 구현한 방식은 아래와 같다.

  • 두 구슬의 위치를 저장하는 구조체(MARBLE_POS)를 선언하고, 이를 이용한 bfs 알고리즘을 사용한다.
  • bfs 알고리즘에 필요한 visited 배열은 두 구슬의 위치를 기반으로 나타낼 수 있다. 예를 들어, 빨간 구슬이 (1,1) 위치이고, 파란 구슬이 (1,2) 위치라면 visited[1][1][1][2] = true; 로 표기한다. 구슬의 위치 이외의 맵의 다른 요소들은 위치가 항상 동일하므로 구슬의 위치만으로 방문 여부를 나타내는 것이 가능하다.
  • MARBLE_POS의 cnt가 11 이상일 경우 -1을 출력한다.

구현한 코드는 아래와 같다.

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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

typedef struct marblepos {
    int rx, ry, bx, by, cnt;
    marblepos(int _ry, int _rx, int _by, int _bx, int _cnt): rx(_rx), ry(_ry), bx(_bx), by(_by), cnt(_cnt) {};
}MARBLE_POS;

queue<MARBLE_POS> que;
bool visited[10][10][10][10];
char board[10][10];
int n,m;

pair<int, int> move(int y, int x, int opy, int opx, int dir) {
    // 동, 서 움직임
    if(dx[dir] != 0) {
        while((y != opy || x + dx[dir] != opx) && board[y][x + dx[dir]] == '.')
            x += dx[dir];
        // 구멍에 막혀 구슬이 전진을 못했을 수 있다. 이 경우를 처리하는 분기
        if(board[y][x + dx[dir]] == 'O')
            x += dx[dir];
    }
    // 남, 북 움직임
    else {
        while((y + dy[dir] != opy || x != opx) && board[y + dy[dir]][x] == '.')
            y += dy[dir];
        // 구멍에 막혀 구슬이 전진을 못했을 수 있다. 이 경우를 처리하는 분기
        if(board[y + dy[dir]][x] == 'O')
            y += dy[dir];
    }

    return {y, x};
}

int bfs(int ry, int rx, int by, int bx, int oy, int ox) {
    que.push({ry, rx, by, bx, 0});
    visited[ry][rx][by][bx] = true;

    while(!que.empty()) {
        int ry = que.front().ry;
        int rx = que.front().rx;
        int by = que.front().by;
        int bx = que.front().bx;
        int cnt = que.front().cnt;
        que.pop();

        if(cnt > 10)
            break;

        if(ry == oy && rx == ox)
            return cnt;
        
        // 동, 서, 남, 북
        for(int i=0; i<4; ++i) {
            pair<int, int> nrpos;
            pair<int, int> nbpos;

            // 두 구슬이 같은 행에 위치하고, 오른쪽으로 기울일 때
            if(i == 0 && ry == by) {
                // 빨간 구슬이 파란 구슬보다 왼쪽에 있다면 파란 구슬을 먼저 오른쪽으로 이동시켜야한다.
                if(rx < bx) {
                    nbpos = move(by, bx, ry, rx, i);
                    nrpos = move(ry, rx, nbpos.first, nbpos.second, i);
                } else {
                    nrpos = move(ry, rx, by, bx, i);
                    nbpos = move(by, bx, nrpos.first, nrpos.second, i);
                }
            } else if(i == 1 && ry == by) {
                if(rx < bx) {
                    nrpos = move(ry, rx, by, bx, i);
                    nbpos = move(by, bx, nrpos.first, nrpos.second, i);
                } else {
                    nbpos = move(by, bx, ry, rx, i);
                    nrpos = move(ry, rx, nbpos.first, nbpos.second, i);
                }
            } else if(i == 2 && rx == bx) {
                if(ry < by) {
                    nbpos = move(by, bx, ry, rx, i);
                    nrpos = move(ry, rx, nbpos.first, nbpos.second, i);
                } else {
                    nrpos = move(ry, rx, by, bx, i);
                    nbpos = move(by, bx, nrpos.first, nrpos.second, i);
                }
            } else if(i == 3 && rx == bx) {
                if(ry < by) {
                    nrpos = move(ry, rx, by, bx, i);
                    nbpos = move(by, bx, nrpos.first, nrpos.second, i);
                } else {
                    nbpos = move(by, bx, ry, rx, i);
                    nrpos = move(ry, rx, nbpos.first, nbpos.second, i);
                }
            } else {
                nrpos = move(ry, rx, by, bx, i);
                nbpos = move(by, bx, ry, rx, i);
            }

            int nry = nrpos.first;
            int nrx = nrpos.second;
            int nby = nbpos.first;
            int nbx = nbpos.second;
            int ncnt = cnt + 1;
    
            if(visited[nry][nrx][nby][nbx])
                continue;
            // 파란 구슬이 홀 통과하는 경우
            if(nby == oy && nbx == ox)
                continue;
            
            visited[nry][nrx][nby][nbx] = true;
            que.push({nry, nrx, nby, nbx, ncnt});
        }
    }

    return -1;
}

int main(void) {
    scanf("%d %d", &n, &m);
    
    int rx, ry, bx, by, ox, oy;
    for(int i=0; i<n; ++i) {
        for(int j=0; j<m; ++j) {
            scanf(" %c", &board[i][j]);
            if(board[i][j] == 'R') {
                rx = j; ry = i;
            } else if(board[i][j] == 'B') {
                bx = j; by = i;
            } else if(board[i][j] == 'O') {
                ox = j; oy = i;
            }
            
            if(board[i][j] != '#' && board[i][j] != 'O')
                board[i][j] = '.';
        }
    }
    

    printf("%d", bfs(ry, rx, by, bx, oy, ox));
}
0%