[백준 13460] 구슬 탈출 2 (삼성 SW 역량 테스트 기출 문제)

# 문제 링크

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

# 접근 방법

• 빨간색 구슬과 파란색 구슬의 위치와 이동 횟수를 기록하는 구조체를 만들었다.
• 최소 이동 횟수를 구하는 것이기 때문에 BFS 알고리즘을 활용했다.
• 빨간색 구슬과 파란색 구슬이 부딛히는 경우를 생각했다.

# 실패 기록

빨간색 구슬과 파란색 구슬이 이동할 수 있는 모든 경우를 생각했었다. 하지만 그렇게 하니 if-else문이 많아져 알고리즘의 분기가 많아졌고, 나도 모르게 놓치는 경우가 발생해서 정답을 이끌어낼 수 없었다. 따라서 모든 경우를 생각하기보다는 구슬의 움직임을 몇 가지 경우로 일반화하기로 했다.

# 포인트

• 방문을 체크하는 visited 배열을 4차원으로 만들어서 빨간색 구슬과 파란색 구슬의 가능한 모든 위치를 기록해야 한다.
• 두 구슬을 일단 먼저 굴려주고, 빨간색 구슬과 파란색 구슬이 부딛히는 경우(위치가 같아질 경우)에는 굴리기 전의 위치를 비교해가면서 한 구슬의 위치를 한 칸 이동시켜줘야 한다.

# 소스코드

#include <iostream>
#include <queue>

using namespace std;

char board[10][10];
bool visited[10][10][10][10]; // y_red, x_red, y_blue, x_blue
int y_dir[4] = {-1, 0, 1, 0}; // up, right, down, left
int x_dir[4] = {0, 1, 0, -1};

struct position{
    int y_red, x_red, y_blue, x_blue;
    int move_cnt;
};

void move(int& y, int& x, int dir) {
    while (true) {
        y += y_dir[dir]; x += x_dir[dir];
        if (board[y][x] == '#') {
            y -= y_dir[dir]; x -= x_dir[dir];
            break;
        }
        else if (board[y][x] == 'O')
            break;
    }
}

int main(int argc, const char * argv[]) {
    int n, m;
    cin >> n >> m;
    
    int y_des, x_des, y_red, x_red, y_blue, x_blue;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char input;
            cin >> input;
            board[i][j] = input;
            if (input == 'R') {
                y_red = i; x_red = j;
            }
            else if (input == 'B') {
                y_blue = i; x_blue = j;
            }
            else if (input == 'O') {
                y_des = i; x_des = j;
            }
        }
    }
    
    int ans = -1;
    queue<position> q;
    q.push({y_red, x_red, y_blue, x_blue, 0});
    visited[y_red][x_red][y_blue][x_blue] = true;
    
    while (!q.empty()) {
        position pos = q.front();
        q.pop();
        
        if (pos.move_cnt > 10) break;
        
        if (pos.y_red == y_des && pos.x_red == x_des) {
            ans = pos.move_cnt;
            break;
        }
        
        for (int i = 0; i < 4; i++) {
            int y_red = pos.y_red, x_red = pos.x_red;
            int y_blue = pos.y_blue, x_blue = pos.x_blue;
            
            move(y_red, x_red, i);
            move(y_blue, x_blue, i);
            
            if (y_blue == y_des && x_blue == x_des) continue;
            
            if (y_red == y_blue && x_red == x_blue) {
                switch (i) {
                    case 0: // up
                        pos.y_red > pos.y_blue ? y_red++ : y_blue++;
                        break;
                    case 1: // right
                        pos.x_red > pos.x_blue ? x_blue-- : x_red--;
                        break;
                    case 2: // down
                        pos.y_red > pos.y_blue ? y_blue-- : y_red--;
                        break;
                    case 3: // left
                        pos.x_red > pos.x_blue ? x_red++ : x_blue++;
                        break;
                }
            }
            
            if (!visited[y_red][x_red][y_blue][x_blue]) {
                q.push({y_red, x_red, y_blue, x_blue, pos.move_cnt + 1});
                visited[y_red][x_red][y_blue][x_blue] = true;
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}