[백준] 13460 구슬 찾기2 BFS

문제 :

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

분석 :

이 문제는 삼성 어쩌구 역량 기출 문제였다. 아직 기출 문제에 대한 감이 없다. 기업 코딩테스트는 다 기업 코딩테스트 같아서 말이다 하하

어쩼든 그래프 이론을 복습하는 와중에 한번 풀어볼까 ? 해서 도전하게 되었다. 문제를 읽다가 이해가 되면 문제 포기를 못하겠다.

input 받는것만 만들고 다른 블로그님들의 글을 참고하여 겨우 겨우 풀었다. 이 마저도 예외 처리를 하지 않아 계속 틀리다가 겨우 테스트 케이스가 옜다 하고 맞춰준 느낌 .. 

 

백준 질문 글을 통해 visit 배열을 4차원으로 해야 하는 이유를 알게 되었다. 구슬이 동시에 통과할 수도 있기 때문에 빨간 구슬과 파란 구슬의 방문 여부를 같이 검사해야한다는 것! 그래서 4차원 배열을 써야 한다고 했다. 그리고 방문된 곳을 또 간다는 뜻은 왔던 길을 반복하는 것이기 때문에 10번 안에 통과하지 못할수도 있어 왔던 길을 가지 않아야 한다는 뜻을 암시하고 있다고 한다.

 

그리고 또 신기한 점은 같은 방향으로 기울였을 때 구슬이 같은 인덱스에 같이 머무를수가 있을텐데 그러면 안되므로 이전 위치에서 움직인 위치로 간 길이가 더 많은 친구의 인덱스 값을 왔던 방향으로 하나 감소시켜준다고 한다! 

 

여러모로 신기한 것들이 많았던 문제였다 글고 넘 어렵다 ㅜ  

 

c++ 코드 :

//
//  13460_marbleEscape2.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/04/22.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <math.h>

using namespace std;

char map[11][11];
bool visit[11][11][11][11] = {false, };


int N, M;

pair<int, int> redStart;
pair<int, int> blueStart;
pair<int, int> holeStart;

int dx[] = { 0, 0, 1, -1 }; //up down left right
int dy[] = { 1, -1, 0, 0 };

int find_hole_bfs(){
    queue<pair<pair<int, int>, pair<int, int>>>q; // red꺼, blue꺼
    q.push({redStart, blueStart}); // 큐에 red blue꺼 x, y 순으로 push
    visit[redStart.first][redStart.second][blueStart.first][blueStart.second] = true;
    int result = 0; //답
    
    if(result == 10){
        return -1;
    }
    
    while(!q.empty()){
        int size = (int)q.size();
        while(size--){

        pair<pair<int, int>, pair<int, int>> cur = q.front();
        q.pop();
        
        int redX = cur.first.first;
        int redY = cur.first.second;
        int blueX = cur.second.first;
        int blueY = cur.second.second;
        
        if(map[redX][redY] == 'O' && map[redX][redY] != map[blueX][blueY]){ // 구멍을 찾으면 근데 같이 통과하지 않으면
            return result;
        }
            
        
        // 움직이자
        for(int i =0; i < 4; i++){
            int nextRedX = redX;
            int nextRedY = redY;
            int nextBlueX = blueX;
            int nextBlueY = blueY;

            while(map[nextRedX + dx[i]][nextRedY + dy[i]] != '#' && map[nextRedX][nextRedY] != 'O'){
                nextRedX += dx[i];
                nextRedY += dy[i];
            }
            
            while(map[nextBlueX + dx[i]][nextBlueY + dy[i]] !='#' && map[nextBlueX][nextBlueY] != 'O'){
                nextBlueX += dx[i];
                nextBlueY += dy[i];
            }
    
            if(map[nextBlueX][nextBlueY] == 'O') // 파란 공이 먼저 도착했을 경우 예외처리!! 이부분 안해서 틀렸다.
            {
                continue;
            }
            
            if(nextRedX == nextBlueX && nextRedY == nextBlueY){ // 두 공의 위치가 같다면
                //움직인 거리로 누가 뒤에 갈지 판별
                if(map[nextRedX][nextRedY] == 'O')
                {
                    continue;
                }
                
                if(abs(nextRedX- redX) + abs(nextRedY - redY) < abs(nextBlueX - blueX) + abs(nextBlueY - blueY)){
                    nextBlueX -= dx[i];
                    nextBlueY -= dy[i];
                }else{
                    nextRedX -= dx[i];
                    nextRedY -= dy[i];
                }
            }
            
            if (visit[nextRedX][nextRedY][nextBlueX][nextBlueY]) continue; // 방문 했다면 무시
            visit[nextRedX][nextRedY][nextBlueX][nextBlueY] = true; // 방문 표시
            q.push({ {nextRedX,nextRedY}, {nextBlueX, nextBlueY}});
        }
    }
    if (result >= 10) return -1; // 문제 조건
    result++;
        
        
        
    }
    
    return -1; // queue가 비어있을때
}

int main(){
    cin >> N >> M;
    for(int i = 1; i<= N; i++){
        for(int j = 1; j<= M; j++){
            char temp;
            cin >> temp;
            if(temp == 'R'){
                redStart = make_pair(i, j); // 빨간 구슬 시작 위치 기록
            }else if(temp == 'B'){
                blueStart = make_pair(i, j);
            }else if(temp == 'O'){
                holeStart = make_pair(i, j);
            }
            map[i][j] = temp;
        }
    }
    
//    for(int i = 1; i<= N; i++){
//        for(int j = 1; j<= M; j++){
//            cout << map[i][j] << " ";
//        }
//        cout <<'\n';
//    }
    
    cout << find_hole_bfs() << '\n';
    
    return 0;
}