BOJ : 13459 째로탈출

문제 : https://www.acmicpc.net/problem/13459

2016년 삼성 하반기 공채 SW 역량테스트 오전 문제

더러운 BFS 문제이다. 백준에 오후 기출문제는 정확히 구현되어있지 않지만 오전 문제는 거의 비슷하게 구현되어있다.

개인적으로 오전문제가 오후문제보다 어려웠던 것 같다.

판을 돌려 두개의 구슬을 움직여 10번안에 빨간 구슬을 꺼낼 수 있는가가 문제의 핵심이다.

판을 돌린다고 했지만 구슬만 상하좌우로 옮기면 된다.

문제 핵심

1. 빨간 구슬과 파란 구슬의 visited배열을 하나로 관리

2. 빨간 구슬과 파란 구슬 서로의 위치는 상관없이 상하좌우 이동 후 방향에 따라 구슬의 위치관계 고려해주고 조정한다.

3. 파란 구슬이 빠져 나오는 경우는 무시 (빨간 구슬이 먼저나와도 파란 구슬이 같이 나오면 무쓸모)

삼성 SW 역량테스트는 조건이 많기 때문에 상하좌우 코드를 일일이 만들게 되면 코드양이 많아져 디버깅할 때 고생한다. 

코드를 줄이는 습관을 기르자.

비슷한 문제

13460 째로탈출 2 - 최소 횟수를 출력

2016년 삼성 하반기 공채 SW 역량테스트 문제

12100 2048(Easy) / 해설  오전

3190 뱀  오후

#include <cstdio>
#include <queue>
using namespace std;
 
struct Pos{
public:
    int redR, redC, blueR, blueC;
    Pos(){}
    Pos(int rr,int rc,int br, int bc): redR(rr), redC(rc), blueR(br), blueC(bc){}
};
int N,M,cnt=0;
char board[12][12];
bool visited[12][12][12][12];
int pr[4]={0,0,1,-1};
int pc[4]={1,-1,0,0};
queue<Pos> marble;
 
int main(){
    scanf("%d%d",&N,&M);
    
    int a,b,c,d;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            scanf(" %c",&board[i][j]);
            if(board[i][j]=='R')
                a=i, b=j;
            
            if(board[i][j]=='B')
                c=i, d=j;
            
        }
    }
    visited[a][b][c][d] = 1;
    marble.push(Pos(a,b,c,d));
    
    while(!marble.empty()){
        int sz = marble.size();
        while(sz--){
            int br = marble.front().blueR, bc = marble.front().blueC;
            int rr = marble.front().redR, rc = marble.front().redC;
            marble.pop();
            
            if(board[rr][rc]=='O'){
                printf("1\n");
                return 0;
            }
            for(int i=0;i<4;i++){
                int nbr=br, nbc=bc, nrr=rr, nrc=rc;
                bool bf=0;
                //move red marble
                while(board[nrr+pr[i]][nrc+pc[i]]!='#' && board[nrr][nrc]!='O'){
                    nrr += pr[i];
                    nrc += pc[i];
                }
                //move blue marble
                while(board[nbr+pr[i]][nbc+pc[i]]!='#' && board[nbr][nbc]!='O'){
                    nbr += pr[i];
                    nbc += pc[i];
                    if(board[nbr][nbc]=='O') bf=1;
                }
                if((nrr == nbr && nrc == nbc)){
                    if(i==0) {
                        if(bc>rc) nrc-=1;
                        else nbc-=1;
                    }
                    else if(i==1){
                        if(bc>rc) nbc+=1;
                        else nrc +=1;
                    }
                    else if(i==2){
                        if(br>rr) nrr-=1;
                        else nbr-=1;
                    }
                    else {
                        if(br>rr) nbr+=1;
                        else nrr+=1;
                    }
                }
                if(bf) continue;
                if(visited[nrr][nrc][nbr][nbc]) continue;
                marble.push(Pos(nrr,nrc,nbr,nbc));
                visited[nrr][nrc][nbr][nbc]=1;
            }
        }
        cnt++;
        if(cnt>10) break;
    }
    printf("0\n");
}