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

문제

 

---

풀이

 

비트마스크로도 풀 수 있다는데 난 백트래킹으로 풀었다. 근데 bfs로도 풀 수 있나보다.

먼저 상하좌우에 대해 각 구슬의 새로운 위치를 찾는다.

직전에 갔던 방향으로 또 이동할 필요는 없으니 그 방향은 제외한다.

 

두 구슬의 위치변화가 없거나 파란구슬이 빠진 경우는 제외한다.

만약 두 구슬의 새로운 위치가 같다면 같은 칸에 구슬이 2개 있을 수는 없으니 원래의 선후관계를 따져 구슬을 이동한다.

이동 횟수가 10을 넘어가거나 현재의 최솟값을 넘어가면 더이상 탐색하지 않는다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;
typedef pair<int, int> pp;

int result = 11;
vector<vector<char>> board;
pp dir[4] = {{-1, 0},  //상
             {1,  0},  //하
             {0,  -1}, //좌
             {0,  1}}; //우

pp newPos(pp pos, int d) {
    int r = pos.first; //행
    int c = pos.second; //열
    while ((board[r][c] != '#') && (board[r][c] != 'O')) { //벽 또는 구멍을 만날 때까지 이동
        r += dir[d].first;
        c += dir[d].second;
    }
    if (board[r][c] == 'O') //구멍에 빠짐
        return make_pair(-1, -1);
    return make_pair(r - dir[d].first, c - dir[d].second); //벽을 만남
}

int forwardMarble(vector<pp> marble, int d) { //특정 방향에 대해 어떤 구슬이 앞에 있었는지
    int r = marble[0].first - marble[1].first;
    int c = marble[0].second - marble[1].second;
    if (((r ^ dir[d].first) >= 0) && ((c ^ dir[d].second) >= 0)) //r, c의 부호가 dir과 같다면 빨간 구슬이 앞에 있었던 것
        return 1;
    return 0;
}

void backtracking(int cnt, vector<pp> marble, int before_dir) {
    if (cnt >= result) //cnt가 result 이상이라면 더이상 탐색할 필요 없음
        return;
    vector<pp> new_pos; //각 구슬의 새로운 위치
    new_pos.assign(2, make_pair(0, 0));
    for (int i = 0; i < 4; i++) {
        if (i == before_dir) //직전과 같은 방향은 탐색할 필요 없음
            continue;
        int kept_cnt = 0; //위치 변화 없는 구슬의 수
        for (int j = 0; j < 2; j++) {
            new_pos[j] = newPos(marble[j], i);
            if ((new_pos[j].first == marble[j].first) && (new_pos[j].second == marble[j].second)) //위치 변화 없음
                kept_cnt++;
        }
        if ((kept_cnt == 2) ||
            ((new_pos[1].first == -1) && (new_pos[1].second == -1))) //두 구슬 모두 위치가 그대로거나 파란 구슬이 구멍에 빠졌을 때
            continue;
        if ((new_pos[0].first == -1) && (new_pos[0].second == -1)) { //빨간 구슬이 구멍에 빠졌다면 최솟값 갱신
            result = min(result, cnt + 1);
            return;
        } else {
            if ((new_pos[0].first == new_pos[1].first) &&
                (new_pos[0].second == new_pos[1].second)) { //두 구슬의 새로운 위치가 같다면
                int backward_marble = forwardMarble(marble, i); //뒤에 있는 구슬의 인덱스
                new_pos[backward_marble].first -= dir[i].first;
                new_pos[backward_marble].second -= dir[i].second;
            }
            backtracking(cnt + 1, new_pos, i); //새로운 위치에 대한 백트래킹 호출
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    string input;
    vector<pp> marble; //구슬의 초기 위치

    cin >> N >> M;
    board.assign(N, vector<char>(M));
    marble.assign(2, make_pair(0, 0));
    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j] = input[j];
            if (board[i][j] == 'R') //빨간 구슬
                marble[0] = make_pair(i, j);
            else if (board[i][j] == 'B') //파란 구슬
                marble[1] = make_pair(i, j);
        }
    }
    backtracking(0, marble, -1); //백트래킹
    cout << ((result == 11) ? -1 : result);
}

전체 소스코드다.

 

    for (int i = 0; i < N; i++) {
        cin >> input;
        for (int j = 0; j < M; j++) {
            board[i][j] = input[j];
            if (board[i][j] == 'R') //빨간 구슬
                marble[0] = make_pair(i, j);
            else if (board[i][j] == 'B') //파란 구슬
                marble[1] = make_pair(i, j);
        }
    }

먼저 보드의 초기 상태를 입력 받으며 각 구슬의 위치를 저장해 둔다.

 

    backtracking(0, marble, -1); //백트래킹
    cout << ((result == 11) ? -1 : result);

그리고 백트래킹 함수를 호출한다.

 

void backtracking(int cnt, vector<pp> marble, int before_dir) {
    if (cnt >= result) //cnt가 result 이상이라면 더이상 탐색할 필요 없음
        return;
    vector<pp> new_pos; //각 구슬의 새로운 위치
    new_pos.assign(2, make_pair(0, 0));
    for (int i = 0; i < 4; i++) {
        if (i == before_dir) //직전과 같은 방향은 탐색할 필요 없음
            continue;
        int kept_cnt = 0; //위치 변화 없는 구슬의 수
        for (int j = 0; j < 2; j++) {
            new_pos[j] = newPos(marble[j], i);
            if ((new_pos[j].first == marble[j].first) && (new_pos[j].second == marble[j].second)) //위치 변화 없음
                kept_cnt++;
        }
        if ((kept_cnt == 2) ||
            ((new_pos[1].first == -1) && (new_pos[1].second == -1))) //두 구슬 모두 위치가 그대로거나 파란 구슬이 구멍에 빠졌을 때
            continue;
        if ((new_pos[0].first == -1) && (new_pos[0].second == -1)) { //빨간 구슬이 구멍에 빠졌다면 최솟값 갱신
            result = min(result, cnt + 1);
            return;
        } else {
            if ((new_pos[0].first == new_pos[1].first) &&
                (new_pos[0].second == new_pos[1].second)) { //두 구슬의 새로운 위치가 같다면
                int backward_marble = forwardMarble(marble, i); //뒤에 있는 구슬의 인덱스
                new_pos[backward_marble].first -= dir[i].first;
                new_pos[backward_marble].second -= dir[i].second;
            }
            backtracking(cnt + 1, new_pos, i); //새로운 위치에 대한 백트래킹 호출
        }
    }
}

백트래킹 함수다.

 

    if (cnt >= result) //cnt가 result 이상이라면 더이상 탐색할 필요 없음
        return;

현재의 이동횟수가 result보다 크다면 non-promising이다.

 

    for (int i = 0; i < 4; i++) {
        if (i == before_dir) //직전과 같은 방향은 탐색할 필요 없음
            continue;
        int kept_cnt = 0; //위치 변화 없는 구슬의 수
        for (int j = 0; j < 2; j++) {
            new_pos[j] = newPos(marble[j], i);
            if ((new_pos[j].first == marble[j].first) && (new_pos[j].second == marble[j].second)) //위치 변화 없음
                kept_cnt++;
        }
        if ((kept_cnt == 2) ||
            ((new_pos[1].first == -1) && (new_pos[1].second == -1))) //두 구슬 모두 위치가 그대로거나 파란 구슬이 구멍에 빠졌을 때
            continue;
        if ((new_pos[0].first == -1) && (new_pos[0].second == -1)) { //빨간 구슬이 구멍에 빠졌다면 최솟값 갱신
            result = min(result, cnt + 1);
            return;
        } else {
            if ((new_pos[0].first == new_pos[1].first) &&
                (new_pos[0].second == new_pos[1].second)) { //두 구슬의 새로운 위치가 같다면
                int backward_marble = forwardMarble(marble, i); //뒤에 있는 구슬의 인덱스
                new_pos[backward_marble].first -= dir[i].first;
                new_pos[backward_marble].second -= dir[i].second;
            }
            backtracking(cnt + 1, new_pos, i); //새로운 위치에 대한 백트래킹 호출
        }
    }

구슬을 상하좌우로 이동해본다.

 

        if (i == before_dir) //직전과 같은 방향은 탐색할 필요 없음
            continue;

이전과 같은 방향은 탐색할 필요 없다.

 

        for (int j = 0; j < 2; j++) {
            new_pos[j] = newPos(marble[j], i);
            if ((new_pos[j].first == marble[j].first) && (new_pos[j].second == marble[j].second)) //위치 변화 없음
                kept_cnt++;
        }

각 구슬의 새로운 위치를 new_pos에 저장하고 만약 위치 변화가 없다면 kept_cnt를 늘려준다.

 

pp newPos(pp pos, int d) {
    int r = pos.first; //행
    int c = pos.second; //열
    while ((board[r][c] != '#') && (board[r][c] != 'O')) { //벽 또는 구멍을 만날 때까지 이동
        r += dir[d].first;
        c += dir[d].second;
    }
    if (board[r][c] == 'O') //구멍에 빠짐
        return make_pair(-1, -1);
    return make_pair(r - dir[d].first, c - dir[d].second); //벽을 만남
}

새로운 위치는 이렇게 찾는다.

벽 또는 구멍을 만날때까지 입력받은 방향으로 이동하고,

while문이 종료됐을 때 board[r][c]의 값을 확인한다.

만약 'O'라면 구멍에 빠진 것이므로 (-1, -1)을 리턴하고, 아니라면 벽을 만나 종료된 것이니 그 이전 좌표를 리턴한다.

 

        if ((kept_cnt == 2) ||
            ((new_pos[1].first == -1) && (new_pos[1].second == -1))) //두 구슬 모두 위치가 그대로거나 파란 구슬이 구멍에 빠졌을 때
            continue;

이렇게 새로운 좌표를 구했을 때,

만약 kept_cnt가 2라면 두 구슬 모두 이동하지 않을 것이고

파란 구슬의 좌표가 (-1, -1)이라면 파란 구슬이 구멍에 빠진 것이다. 이 경우는 탐색하지 않는다.

 

        if ((new_pos[0].first == -1) && (new_pos[0].second == -1)) { //빨간 구슬이 구멍에 빠졌다면 최솟값 갱신
            result = min(result, cnt + 1);
            return;
        }

빨간 구슬의 좌표가 (-1, -1)이라면 빨간 구슬이 구멍에 빠진 것이니 최솟값을 갱신한다.

 

        else {
            if ((new_pos[0].first == new_pos[1].first) &&
                (new_pos[0].second == new_pos[1].second)) { //두 구슬의 새로운 위치가 같다면
                int backward_marble = forwardMarble(marble, i); //뒤에 있는 구슬의 인덱스
                new_pos[backward_marble].first -= dir[i].first;
                new_pos[backward_marble].second -= dir[i].second;
            }
            backtracking(cnt + 1, new_pos, i); //새로운 위치에 대한 백트래킹 호출
        }

그렇지 않을 경우엔 새로운 위치에 대해 백트래킹 함수를 호출해야 하는데,

그 전에 혹시 두 구슬의 위치가 겹치진 않았는지 확인한다.

 

같은 칸에 2개의 구슬이 있을 순 없기 때문이다.

만약 그렇다면 forwardMarble 함수를 호출해서 둘 중 뒤에 있던 구슬의 인덱스를 구하고 한칸 뒤로 이동시킨다.

 

int forwardMarble(vector<pp> marble, int d) { //특정 방향에 대해 어떤 구슬이 앞에 있었는지
    int r = marble[0].first - marble[1].first;
    int c = marble[0].second - marble[1].second;
    if (((r ^ dir[d].first) >= 0) && ((c ^ dir[d].second) >= 0)) //r, c의 부호가 dir과 같다면 빨간 구슬이 앞에 있었던 것
        return 1;
    return 0;
}

방향에 대한 구슬의 선후관계는 이렇게 구한다.

두 수의 부호가 같은지 아닌지 확인하는 방법은

https://real-012.tistory.com/78

두 수의 부호가 같은지 다른지 확인하는 방법[XOR], C++, 코딩스킬

여기서 봤다.

 

            backtracking(cnt + 1, new_pos, i); //새로운 위치에 대한 백트래킹 호출

이렇게 위치에 대한 보정을 마치면 새로운 위치에 대한 백트래킹 함수를 호출한다.