백준 g1 13460 구슬 탈출 2 c++

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

13460번: 구슬 탈출 2

 

문제 설명

• 가장자리가 벽으로 막혀있는 판 안에 빨간 구슬 R, 파란 구슬 B, 빠져나가는 구멍 O 존재
• 판을 상하좌우로 기울여서 빨간 구슬 R을 구멍으로 빠져나가도록 해야 함
• 이때 파란 구슬 B가 구멍으로 나가거나, 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져나가면 안 됨

풀이

 

1. 기울이기 방향

4가지로 움직일 수 있고, 최대 10번 이므로 4^10 = 대략 10^6, 모든 경우의 수를 다 탐색할 수 있음

 

dfs : k번째 움직임 (0부터 시작), prev는 이전의 방향 (같은 방향은 연속해서 기울일 필요 없음)

dfs(int k, int prev)
	if move == 10
    	return
    for(dir: 0 ~ 3)
    	if dir == prev return
        
        prevR, prevB 위치 저장
        tilt(dir) 기울이기
        
        if 이상 없으면
        	dfs (k+1, dir)
            되돌리기
        else if 빨간 구슬 들어감
        	mx = max(mx, k+1)
            되돌리기
        else 파란 구슬 들어감
        	되돌리기

 

2. 기울여서 구슬 움직이기

 

2-1. 빨간 구슬, 파란 구슬 중 선 정하기

움직이는 거 자체는 while문을 써서 장애물을 만날 때까지 이동시켜 주면 되지만, 구슬이 2개일 경우 어느 구슬을 먼저 움직이냐에 따라 값이 달라질 수 있다(ex. [ . . . RB ] 인 경우 B를 먼저 움직이려고 하면 R 때문에 이동하지 못함).

 

이는 방향에 따라 어느 구슬을 먼저 움직일지 정해줌으로써 해결할 수 있다. 

 

기울이는 방향이 상 -> i가 작은 애부터, 하 -> i가 큰 애부터, 좌 -> j가 작은 애부터, 우 -> j가 큰 애부터 먼저 움직여준다.

 

2-2. 구슬이 함께 들어가는 경우 체크

경우에 따라 빨간 구슬 이동 -> 파란 구슬 이동 일 수 있는데, 빨간 구슬이 구멍에 들어가고 나서 파란 구슬 역시 구멍에 들어갈 수 있다. 이때는 성공이 아니라 실패로 체크해야 한다.

 

tilt는 방향 dir을 받아서 기울이고, 결과가 어떤지 return하는 함수

int tilt(int dir) { // 0 킵고잉 1 빨간 구슬 들어감 2 파란 구슬 들어감
    if (dir == 0) { // 상, i 좌표 작은 애부터
        if (curR.first < curB.first) {
            int res = move(curR, dir);
            if (move(curB, dir)) return 2;

            if (res) return 1;
        } else {
            if (move(curB, dir)) return 2;
            if (move(curR, dir)) return 1;
        }
    } else if (dir == 1) { // 좌, j 좌표 작은 애부터
        동일
    } else if (dir == 2) { // 하, i 좌표 큰 애부터
        동일
    } else if (dir == 3) { // 우, j 좌표 큰 애부터
		동일
    }

    return 0;
}

 

move는 구슬의 위치와 방향을 받아서 실제로 구슬을 움직이고, 구멍에 들어갔으면 true 그렇지 않으면 false를 반환하는 함수

bool move(pair<int, int> cur, int dir) { // 구멍에 들어가면 true, 들어가지 않으면 false를 return
    char marble = board[cur.first][cur.second];
    while (1) {
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];

        if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
        if (board[nx][ny] == '#') break;
        if (board[nx][ny] == 'R' || board[nx][ny] == 'B') break;

        if (board[nx][ny] == 'O') {
            board[cur.first][cur.second] = '.';

            return true;
        }

        board[nx][ny] = board[cur.first][cur.second];
        board[cur.first][cur.second] = '.';

        cur.first = nx;
        cur.second = ny;
        if (marble == 'R') {
            curR.first = nx;
            curR.second = ny;
        } else {
            curB.first = nx;
            curB.second = ny;
        }
    }
    return false;
}

 

 

코드

/*boj g1 13460 구슬 탈출 2*/
#include <iostream>
#define MAXN 12
#define MX 99
using namespace std;

int N, M;
string board[MAXN];

int mx = MX;

int dx[4] = {-1, 0, 1, 0}; // 상 좌 하 우
int dy[4] = {0, -1, 0, 1};

pair<int, int> curR;
pair<int, int> curB;

void input() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> board[i];

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (board[i][j] == 'R') {
                curR = make_pair(i, j);
            }

            else if (board[i][j] == 'B') {
                curB = make_pair(i, j);
            }
        }
    }
}

void printBoard() {
    cout << "\n==================\n";
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cout << board[i][j];
        }
        cout << "\n";
    }
}

bool move(pair<int, int> cur, int dir) { // 구멍에 들어가면 true, 들어가지 않으면 false를 return
    char marble = board[cur.first][cur.second];
    while (1) {
        int nx = cur.first + dx[dir];
        int ny = cur.second + dy[dir];

        if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
        if (board[nx][ny] == '#') break;
        if (board[nx][ny] == 'R' || board[nx][ny] == 'B') break;

        if (board[nx][ny] == 'O') {
            board[cur.first][cur.second] = '.';

            return true;
        }

        board[nx][ny] = board[cur.first][cur.second];
        board[cur.first][cur.second] = '.';

        cur.first = nx;
        cur.second = ny;
        if (marble == 'R') {
            curR.first = nx;
            curR.second = ny;
        } else {
            curB.first = nx;
            curB.second = ny;
        }
    }
    return false;
}

int tilt(int dir) { // 0 킵고잉 1 빨간 구슬 들어감 2 파란 구슬 들어감
    /*
        dir == 0 상이면 i좌표가 작은 애 부터
        dir == 1 좌면 j좌표가 작은 애부터
        dir == 2 i좌표 큰 애부터
        dir == 3 j 좌표 큰 애부터
    */

    if (dir == 0) { // 상, i 좌표 작은 애부터
        if (curR.first < curB.first) {
            int res = move(curR, dir);
            if (move(curB, dir)) return 2;

            if (res) return 1;
        } else {
            if (move(curB, dir)) return 2;
            if (move(curR, dir)) return 1;
        }
    } else if (dir == 1) { // 좌, j 좌표 작은 애부터
        if (curR.second < curB.second) {
            int res = move(curR, dir);
            if (move(curB, dir)) return 2;

            if (res) return 1;
        } else {
            if (move(curB, dir)) return 2;
            if (move(curR, dir)) return 1;
        }
    } else if (dir == 2) { // 하, i 좌표 큰 애부터
        if (curR.first > curB.first) {
            int res = move(curR, dir);
            if (move(curB, dir)) return 2;

            if (res) return 1;
        } else {
            if (move(curB, dir)) return 2;
            if (move(curR, dir)) return 1;
        }
    } else if (dir == 3) { // 우, j 좌표 큰 애부터
        if (curR.second > curB.second) {
            int res = move(curR, dir);
            if (move(curB, dir)) return 2;

            if (res) return 1;
        } else {
            if (move(curB, dir)) return 2;
            if (move(curR, dir)) return 1;
        }
    }

    return 0;
}

void dfs(int k, int prev) {
    if (k == 10) {
        return;
    }

    pair<int, int> prevR = make_pair(curR.first, curR.second);
    pair<int, int> prevB = make_pair(curB.first, curB.second);
    for (int dir = 0; dir < 4; dir++) {
        if (dir == prev) continue;

        int isChanged = tilt(dir);

        // if (prevR == curR && prevB == curB) continue;
        // -> 있으면 구멍에 들어갔을 경우, 이전과 같아서 continue해버림

        // printBoard();
        if (!isChanged) { // 0 -> 킵 고잉
            dfs(k + 1, dir);

            board[curR.first][curR.second] = '.';
            board[curB.first][curB.second] = '.';

            board[prevR.first][prevR.second] = 'R';
            board[prevB.first][prevB.second] = 'B';

            curR = prevR;
            curB = prevB;
            continue;
        } else if (isChanged == 1) { // 1 -> 빨간 구슬 들어감
            mx = min(mx, k + 1);

            board[curR.first][curR.second] = '.';
            board[curB.first][curB.second] = '.';

            board[prevR.first][prevR.second] = 'R';
            board[prevB.first][prevB.second] = 'B';
            curR = prevR;
            curB = prevB;
            continue;
        } else { // 2 -> 파란 구슬 들어감
            board[curR.first][curR.second] = '.';
            board[curB.first][curB.second] = '.';

            board[prevR.first][prevR.second] = 'R';
            board[prevB.first][prevB.second] = 'B';
            curR = prevR;
            curB = prevB;
            continue;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    input();
    dfs(0, -1);
    if (mx == MX) mx = -1;
    cout << mx << "\n";
}

 

 

 

실수했던 점

1. curR, curB 와 board 동기화

   - 안 해도 되겠지 하는 부분 빼먹었다가 다 틀림, 놓칠 수 있으니 꼭 다 동기화 해주기

2. dfs 후 되돌리기 할 때 board는 되돌리기 했으면서 curR, curB 값은 되돌리기 안함

   - cur 값은 그대론데 prev만 계속 되돌려서 board에 R, B가 많아짐

 

시뮬레이션을 그래도 많이 풀어보면서 항상 드는 생각은 기본이 중요하다 는 것

문제 그대로 옮기기,

되돌리기 할 때 이전 상태 그대로 옮기기

 

궁금했던 것

https://stackoverflow.com/questions/63522732/are-the-values-stored-in-stdpair-by-reference-or-by-value

Are the values stored in std::pair<> by reference or by value?

c++의 pair는 call by value

무서워서 일일이 값을 복사했는데 그러지 않아도 됨