[C++] 백준 13460번 구슬 탈출 2 풀이

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

13460번: 구슬 탈출 2

문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

 

입력 예시

풀이

이 문제는 방문 빨간 공과 파란 공의 위치가 바뀌었을 때 정확히 어디에 위치하는지를 잘 계산하여야한다. 문제를 본 순간 DFS를 이용하여 풀어야겠다고 생각하였다. 하지만 BFS를 이용하면 더 간단한 풀이가 가능했다. 직접 구현한 코드는 DFS를 이용하였다. DFS를 이용하여 빨간 공, 파란 공이 상하좌우로 기울어졌을 때 멈추는 지점을 계산하였고 공이 동시에 빠지는 지를 판단하였다. 파란 공만 빠지는 경우를 생각해야하므로 파란 공을 먼저 생각하였다. 코드의 실행은 다음과 같다.

 

1. 파란 공이 멈출 때까지 한 방향으로 이동한다.
2. 만약 파란 공이 구멍에 빠진 경우 다른 방향으로 계속한다.
3. 만약 빨간 공이 부딪힌 경우 체크한다. (만약 빨간공이 구멍에 빠질 경우 같이 빠질 수 있고 빨간 공이 멈춘 경우 빨간 공 옆에 멈출 것이기 때문에 지금 위치를 판단할 수 없다)
4. 파란공이 멈춘 위치를 저장하고 빨간공과 부딪히지 않은 경우에만 위치를 배열에서 수정(부딪힌 경우 빨간공에 의해 위치가 결정되므로)
5. 빨간 공이 멈출 때까지 같은 방향으로 이동한다.
6. 만약 구멍에 빠졌을 경우
   • 아까 체크한 파란공이 빨간공과 부딪힌 경우는 파란 공을 원래 위치로 되돌리고 계속 무시
   • 체크되지 않을 경우 depth가 최소값인 경우 정답을 갱신하고 다른 방향으로 계속
7. 빨간 공이 멈춘 위치를 저장하고 빨간공 위치를 배열에서 수정
8. 만약 파란 공이 빨간 공과 부딪힌 경우 파란공 위치를 다 빨간공 옆으로 수정하고 배열에서도 위치 수정
9. DFS로 수정된 빨간 공과 파란 공을 탐색 계속
10. 만약 현재 빨간 공과 파란 공의 위치가 이전에 방문했을 때의 회전 횟수보다 많은 경우는 리턴하여 불필요한 재탐색을 하지 않는다.
11. 그렇지 않은 경우 현재 빨간 공, 파란 공의 위치일 때의 회전 횟수를 갱신하고 탐색을 계속한다.
12. 탐색이 끝난 경우 빨간 공, 파란 공 위치를 다시 되돌리고 다른 방향으로 계속한다.

위 실행 순서를 구현한 코드이다.

코드

#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

const int MN = 11;

string arr[MN];

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

int visit[MN][MN][MN][MN];

int ans = 11;

void dfs(pair<int,int> red, pair<int,int> blue, int depth) {
    if(depth > 10) return; //10번 이상 움직인 경우 리턴
    int redx = red.first, redy = red.second;
    int bluex = blue.first, bluey = blue.second;
    if(visit[redx][redy][bluex][bluey] <= depth) return; //이미 방문한 경우 리턴
    
    visit[redx][redy][bluex][bluey] = depth;

    for(int d = 0; d < 4; d++) { //네 가지 방향으로
        pair<int,int> nblue; //파란공 이동
        int nx = bluex + dx[d]; //다음 파란공 위치
        int ny = bluey + dy[d];
        bool chk = false; //빨간공과 부딪히는지 여부 판단
        while(arr[nx][ny] == '.') { //멈출 때까지
            nx += dx[d];
            ny += dy[d];
        }
        if(arr[nx][ny] == 'O') continue; //파란 공이 구멍에 빠진 경우 계속
        if(arr[nx][ny] == 'R') { //만약 빨간 공을 부딪힌 경우
            chk = true; //부딪혔다고 표시
        }
        nx -= dx[d]; //멈춘 곳으로 위치
        ny -= dy[d];
        nblue = {nx, ny}; //파란공 위치 저장
        
        if(!chk) { //부딪히지 않았을 경우에만 수정
            arr[bluex][bluey] = '.'; //파란공 위치 수정
            arr[nx][ny] = 'B';
        }

        pair<int,int> nred; //빨간공 이동
        nx = redx + dx[d]; //다음 빨간공 위치
        ny = redy + dy[d];
        
        while(arr[nx][ny] == '.') { //멈출 때까지
            nx += dx[d];
            ny += dy[d];
        }
        if(arr[nx][ny] == 'O') { //구멍에 빠진 경우
            if(!chk) {//파란 공이 같이 빠지지 않을 경우에만 정답 갱신
                ans = min(ans, depth+1);
                arr[nblue.first][nblue.second] = '.'; //파란 공 위치 원래대로 돌리고 계속
                arr[bluex][bluey] = 'B';
            }
            continue;
        }
        nx -= dx[d]; //빨간공 멈춘 곳으로 저장
        ny -= dy[d];
        nred = {nx, ny}; //빨간공 위치 저장
        arr[redx][redy] = '.'; //빨간공 위치 수정
        arr[nx][ny] = 'R';

        if(chk) { //만약 파란공이 빨간공과 부딪힌 경우
            nblue.first = nx - dx[d]; //파란공 위치를 빨간공 옆으로 수정
            nblue.second = ny - dy[d];
            arr[nblue.first][nblue.second] = 'B'; //파란공 위치 표시
            arr[bluex][bluey] = '.';
        }
        dfs(nred, nblue, depth+1); //dfs로 탐색 계속
        arr[nred.first][nred.second] = '.'; //빨강, 파란공 위치 처음으로 되돌리기
        arr[nblue.first][nblue.second] = '.';
        arr[redx][redy] = 'R';
        arr[bluex][bluey] = 'B';
    }
}

int main() {
    int N, M; cin >> N >> M;
    fill(&visit[0][0][0][0], &visit[MN-1][MN-1][MN-1][MN], 11); //방문 배열 초기화
    pair<int,int> red;
    pair<int,int> blue;
    for(int i = 0; i < N; i++) {
        cin >> arr[i];
        for(int j = 0; j < arr[i].size(); j++) {
            if(arr[i][j] == 'R') { //빨간공 위치 저장
                red = {i, j};
            }
            if(arr[i][j] == 'B') { //파란공 위치 저장
                blue = {i, j};
            }
        }
    }
    dfs(red, blue, 0);

    if(ans > 10) cout << -1; //10번 이상 걸린 경우 -1출력
    else cout << ans; //그렇지 않은 경우 걸린 횟수 출력
}

복잡해보이고 눈에 확 들어오는 코드는 아니지만 스스로 판단하기에 메모이제이션을 이용해 불필요한 탐색을 줄였다고 생각한다.

생각하지 못한 반례들이 꽤 있어서 질문검색에 있는 반례들을 많이 참고하였다. 빨간공의 좌표, 파란공의 좌표를 출력해보며 잘못 된 부분을 고쳐보며 스스로 풀 수 있었다. 이 문제의 티어는 골드2로 꽤 높은 편이다. 이러한 문제를 많이 풀어봐야할 것 같다.

 

채점 결과