백준 13460번(구슬 탈출 2) c++ 풀이

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

 

 

dfs로 풀었다.. 다 풀고 bfs로도 풀어봤는데 채점 페이지에서 시간이 더 오래 걸린다..!

다른 코드들도 찾아봐야겠다. 나는 뭔가 너무 정직하게만? 구현해서 느린 것 같다. 뭔가뭔가 테크닉이 있겠지

 

 

dfs 기본 틀에서 상하좌우로 기울이는 함수만 구현해서 적용하니까 됐다.

 

보드 상태를 입력받을 때 'R'과 'B'를 빈 칸으로 만들고 대신 구슬들의 x, y 좌표를 따로 관리했다.

 

전역 변수

board: 벽, 구멍, 빈 칸으로만 구성된 보드

whole: 구멍 위치

red/blue: 빨간/파란 구슬 (현재) 위치

 

dfs 돌리는데 나머지 tilt 관련 함수들에서 전역 변수를 조작하기 때문에 red와 blue 값을 저장해놓고 이후에 백업해줬다.

 

d 방향으로 보드를 기울였을 때, 빨간 구슬의 이동과 파란 구슬의 이동을 따로 구현했다.

왜냐하면 기울이는 방향에 따라서 먼저 이동시켜야 하는 구슬이 달라지기 때문이다.

(만약에 ".....RB"인 상황에서 왼쪽으로 기울이는 경우에, B를 먼저 이동시키면 "R....B"가 되어 틀린 결과가 나온다.)

 

먼저 이동시켜야 하는 구슬은 

위로 기울일 때 => 더 위쪽에 있는 구슬

아래로 기울일 때 => 더 아래쪽에 있는 구슬

왼쪽으로 기울일 때 => 더 왼쪽에 있는 구슬

오른쪽으로 기울일 때 => 더 오른쪽에 있는 구슬

 

..

tiltRed 함수는 d 방향으로 보드를 기울일 경우에 빨간 구슬의 최종 위치로 이동 (red 값 갱신)

tiltBlue 함수는  d 방향으로 보드를 기울일 경우에 파란 구슬의 최종 위치로 이동 (blue 값 갱신)

d 방향으로 쭉 가서 도달할 수 있는 마지막 빈 칸으로 이동하는데

다른 구슬이 있는 칸은 갈 수 없으니 이동 전에 'R'과 'B'로 그 자리를 표시했다가 복구했다.

쭉 가다가 구멍을 만나면 구멍 위치에서 멈추도록 했다.

 

두 구슬을 모두 이동시킨 후, 실패인지 성공인지 판단했다.

파란 구슬이 구멍	빨간 구슬이 구멍	결과값 (tilt 반환값)
O	O	-1 (실패)
O	X	-1
X	O	1 (성공)
X	X	0 (성공도 실패도 아님)

 

성공이나 실패라면 더 이상 안 기울여봐도 되고, 그게 아니라면 한 번 더 기울여본다.

 

#include <iostream>

using namespace std;

typedef struct loc{
    int x, y;
}loc;

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

int n, m;
char board[10][10];
loc red, blue, whole;
int ans;

void tiltRed(int d){
    char backup = board[blue.x][blue.y];
    if(board[blue.x][blue.y] != 'O') board[blue.x][blue.y] = 'B';
    
    if(d == 0 || d == 1){ // up or down
        int nxtX = red.x + dx[d];
        
        while(board[nxtX][red.y] == '.'){
            nxtX += dx[d];
        }
        
        red.x = (board[nxtX][red.y] == 'O' ? nxtX : nxtX - dx[d]);
    }
    else{ // left or right
        int nxtY = red.y + dy[d];
        
        while(board[red.x][nxtY] == '.'){
            nxtY += dy[d];
        }
        
        red.y = (board[red.x][nxtY] == 'O' ? nxtY : nxtY - dy[d]);
    }
    
    board[blue.x][blue.y] = backup;
    
    return;
}

void tiltBlue(int d){
    char backup = board[red.x][red.y];
    if(board[red.x][red.y] != 'O') board[red.x][red.y] = 'R';
    
    if(d == 0 || d == 1){
        int nxtX = blue.x + dx[d];
        
        while(board[nxtX][blue.y] == '.'){
            nxtX += dx[d];
        }
        
        blue.x = (board[nxtX][blue.y] == 'O' ? nxtX : nxtX - dx[d]);
    }
    else{
        int nxtY = blue.y + dy[d];
        
        while(board[blue.x][nxtY] == '.'){
            nxtY += dy[d];
        }
        
        blue.y = (board[blue.x][nxtY] == 'O' ? nxtY : nxtY - dy[d]);
    }
    
    board[red.x][red.y] = backup;
    
    return;
}

int tilt(int d){
    bool redFirst = false;
    if(d == 0){
        if(red.x < blue.x) redFirst = true;
    }
    else if(d == 1){
        if(red.x > blue.x) redFirst = true;
    }
    else if(d == 2){
        if(red.y < blue.y) redFirst = true;
    }
    else if(d == 3){
        if(red.y > blue.y) redFirst = true;
    }
    
    if(redFirst){
        tiltRed(d);
        tiltBlue(d);
    }
    else{
        tiltBlue(d);
        tiltRed(d);
    }
    
    if(blue.x == whole.x && blue.y == whole.y) return -1;
    if(red.x == whole.x && red.y == whole.y) return 1;
    
    return 0;
}

void dfs(int cnt){
    if(cnt > 10) return;
    
    for(int d=0; d<4; d++){
        loc r = red, b = blue;
        
        int result = tilt(d);
        
        if(result == 1){
            ans = min(ans, cnt);
        }
        else if(result == -1){
        }
        else if(result == 0){
            dfs(cnt + 1);
        }
        red = r;
        blue = b;
    }
    
    
    return;
}

void solve(){
    ans = 999;
    
    dfs(1);
    
    if(ans == 999) ans = -1;
    
    return;
}

int main(){
    cin >> n >> m;
    
    string str;
    for(int i=0; i<n; i++){
        cin >> str;
        
        for(int j=0; j<m; j++){
            board[i][j] = str[j];
            
            if(board[i][j] == 'R'){
                red = {i, j};
                board[i][j] = '.';
            }
            else if(board[i][j] == 'B'){
                blue = {i, j};
                board[i][j] = '.';
            }
            else if(board[i][j] == 'O'){
                whole = {i, j};
            }
        }
    }
    
    solve();
    
    cout << ans;
    
    return 0;
}

 

 

+

bfs로 하면 더 나을까 하고 해봤는데 아닌 것 같다..

일단은 통과는 되긴하는 코드

#include <iostream>
#include <queue>

using namespace std;

typedef struct loc{
    int x, y;
}loc;
typedef struct qNode{
    loc red, blue;
    int cnt;
}qNode;

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

int n, m;
char board[10][10];
loc red, blue, whole;
int ans;

void tiltRed(int d){
    char backup = board[blue.x][blue.y];
    if(board[blue.x][blue.y] != 'O') board[blue.x][blue.y] = 'B';
    
    if(d == 0 || d == 1){ // up or down
        int nxtX = red.x + dx[d];
        
        while(board[nxtX][red.y] == '.'){
            nxtX += dx[d];
        }
        
        red.x = (board[nxtX][red.y] == 'O' ? nxtX : nxtX - dx[d]);
    }
    else{ // left or right
        int nxtY = red.y + dy[d];
        
        while(board[red.x][nxtY] == '.'){
            nxtY += dy[d];
        }
        
        red.y = (board[red.x][nxtY] == 'O' ? nxtY : nxtY - dy[d]);
    }
    
    board[blue.x][blue.y] = backup;
    
    return;
}

void tiltBlue(int d){
    char backup = board[red.x][red.y];
    if(board[red.x][red.y] != 'O') board[red.x][red.y] = 'R';
    
    if(d == 0 || d == 1){
        int nxtX = blue.x + dx[d];
        
        while(board[nxtX][blue.y] == '.'){
            nxtX += dx[d];
        }
        
        blue.x = (board[nxtX][blue.y] == 'O' ? nxtX : nxtX - dx[d]);
    }
    else{
        int nxtY = blue.y + dy[d];
        
        while(board[blue.x][nxtY] == '.'){
            nxtY += dy[d];
        }
        
        blue.y = (board[blue.x][nxtY] == 'O' ? nxtY : nxtY - dy[d]);
    }
    
    board[red.x][red.y] = backup;
    
    return;
}

int tilt(int d){
    bool redFirst = false;
    if(d == 0){
        if(red.x < blue.x) redFirst = true;
    }
    else if(d == 1){
        if(red.x > blue.x) redFirst = true;
    }
    else if(d == 2){
        if(red.y < blue.y) redFirst = true;
    }
    else if(d == 3){
        if(red.y > blue.y) redFirst = true;
    }
    
    if(redFirst){
        tiltRed(d);
        tiltBlue(d);
    }
    else{
        tiltBlue(d);
        tiltRed(d);
    }
    
    if(blue.x == whole.x && blue.y == whole.y) return -1;
    if(red.x == whole.x && red.y == whole.y) return 1;


    return 0;
}

void bfs(){
    queue<qNode> q;
    
    qNode start;
    start.red = red;
    start.blue = blue;
    start.cnt = 1;
    
    q.push(start);
    
    while(!q.empty()){
        loc currRed = q.front().red;
        loc currBlue = q.front().blue;
        int currCnt = q.front().cnt;
        q.pop();
        
        for(int d=0; d<4; d++){
            red = currRed;
            blue = currBlue;
            
            int result = tilt(d);
            
            if(result == 1){
                ans = currCnt;
                return;
            }
            else if(result == 0 && currCnt < 10){
                qNode nxt;
                nxt.red = red;
                nxt.blue = blue;
                nxt.cnt = currCnt + 1;
                
                q.push(nxt);
            }
        }
        
    }
    
    return;
}

void solve(){
    ans = 999;
    
    bfs();
    
    if(ans == 999) ans = -1;
    
    return;
}

int main(){
    cin >> n >> m;
    
    string str;
    for(int i=0; i<n; i++){
        cin >> str;
        
        for(int j=0; j<m; j++){
            board[i][j] = str[j];
            
            if(board[i][j] == 'R'){
                red = {i, j};
                board[i][j] = '.';
            }
            else if(board[i][j] == 'B'){
                blue = {i, j};
                board[i][j] = '.';
            }
            else if(board[i][j] == 'O'){
                whole = {i, j};
            }
        }
    }
    
    solve();
    
    cout << ans;
    
    return 0;
}