백준 13460번 - 구슬 탈출 2 (C++)

문제

해결 방법

DFS를 사용해서 해결했다... (덕분에 해결 시간은 매우 높다) 실행 방식은 그냥 평범한 DFS... 라서 더 설명할 것이 없다.

구슬의 이동은 따로 구슬의 좌표들을 미리 저장해 구슬을 매번 찾는 손해는 없도록 하였으며, 구현은 그냥 반복을 통하여 이동/탐색하며 빈칸이 아닌 공간을 찾고, 막혀있는 공간을 만난다면 그 바로 이전 칸으로 이동하게끔 하였다. 예외적으로 구멍인 O는 만나면 이동이 아니라 구슬이 삭제되게끔 하였다.

아쉬웠던 점

보자마자 감이 와서 바로 푼 문제인데, BFS로 풀어야 하는데 아무 생각없이 브루트포스(전체탐색)이니 간단한 DFS로 해야겠다~ 라는 안일한 생각을 했다. 사실 최단거리 구하는거면 당연히 BFS를 생각했어야 했는데 수련이 부족한듯 ㅜㅠㅠ

코드

#include <iostream>
#include <vector>
using namespace std;
 
int N, M, Ans = -1;
pair<int, int> Oxy;
 
pair<int, int> Move(vector<vector<char>> &_Map_Vec, int Dir, pair<int, int> _xy) //상1하2좌3우4
{
    int k;
    switch (Dir)
    {
    case 1:
        k = _xy.first - 1;
        while (true)
        {
            if (k < 0 || _Map_Vec[k][_xy.second] != '.')
            {
                if (_Map_Vec[k][_xy.second] != 'O')
                    _Map_Vec[k + 1][_xy.second] = _Map_Vec[_xy.first][_xy.second];
                if(k + 1 != _xy.first || _Map_Vec[k][_xy.second] == 'O')
                    _Map_Vec[_xy.first][_xy.second] = '.';
 
                if(_Map_Vec[k][_xy.second] != 'O')
                    _xy = {k + 1, _xy.second};
                else
                    _xy = { k, _xy.second };
                break;
            }
            k--;
        }
        break;
    case 2:
        k = _xy.first + 1;
        while (true)
        {
            if (k >= N || _Map_Vec[k][_xy.second] != '.')
            {
                if (_Map_Vec[k][_xy.second] != 'O')
                    _Map_Vec[k - 1][_xy.second] = _Map_Vec[_xy.first][_xy.second];
                if (k - 1 != _xy.first || _Map_Vec[k][_xy.second] == 'O')
                    _Map_Vec[_xy.first][_xy.second] = '.';
 
                if (_Map_Vec[k][_xy.second] != 'O')
                    _xy = { k - 1, _xy.second };
                else 
                    _xy = { k, _xy.second };
                break;
            }
            k++;
        }
        break;
    case 3:
        k = _xy.second - 1;
        while (true)
        {
            if (k < 0 || _Map_Vec[_xy.first][k] != '.')
            {
                if (_Map_Vec[_xy.first][k] != 'O')
                    _Map_Vec[_xy.first][k+1] = _Map_Vec[_xy.first][_xy.second];
                if (k + 1 != _xy.second || _Map_Vec[_xy.first][k] == 'O')
                    _Map_Vec[_xy.first][_xy.second] = '.';
 
                if (_Map_Vec[_xy.first][k] != 'O')
                    _xy = { _xy.first, k + 1 };
                else
                    _xy = { _xy.first, k };
 
                break;
            }
            k--;
        }
        break;
    case 4:
        k = _xy.second + 1;
        while (true)
        {
            if (k >= M || _Map_Vec[_xy.first][k] != '.')
            {
                if (_Map_Vec[_xy.first][k] != 'O')
                    _Map_Vec[_xy.first][k - 1] = _Map_Vec[_xy.first][_xy.second];
                if (k - 1 != _xy.second || _Map_Vec[_xy.first][k] == 'O')
                    _Map_Vec[_xy.first][_xy.second] = '.';
 
                if (_Map_Vec[_xy.first][k] != 'O')
                    _xy = { _xy.first, k - 1 };
                else
                    _xy = { _xy.first, k };
 
                break;
            }
            k++;
        }
        break;
    default:
        break;
    }
 
    return _xy;
}
 
void Find(vector<vector<char>> _Map_Vec, int Dir, int Count, pair<int, int> _Rxy, pair<int, int> _Bxy)
{
    bool Check = true;
    //상하좌우
    switch (Dir)
    {
    case 1: 
        // 빨간 구슬이 파랑 구슬과 같은줄이고, 더 아래에 있을 때만 따로 순서 바꿔줌.
        if (_Rxy.second == _Bxy.second && _Rxy.first > _Bxy.first) 
            Check = false;
        break;
    case 2:
        // 빨간 구슬이 파랑 구슬과 같은줄이고, 더 위에 있을 때만 따로 순서 바꿔줌.
        if (_Rxy.second == _Bxy.second && _Rxy.first < _Bxy.first)
            Check = false;
        break;
    case 3:
        // 빨간 구슬이 파랑 구슬과 같은 행 이고, 파랑의 오른쪽에 있을 때만 따로 순서 바꿔줌.
        if (_Rxy.first == _Bxy.first && _Rxy.second > _Bxy.second)
            Check = false;
        break;
    case 4:
        // 빨간 구슬이 파랑 구슬과 같은 행 이고, 파랑의 왼쪽에 있을 때만 따로 순서 바꿔줌.
        if (_Rxy.first == _Bxy.first && _Rxy.second < _Bxy.second)
            Check = false;
        break;
    default:
        break;
    }
    if (Check)
    {
        _Rxy = Move(_Map_Vec, Dir, _Rxy);
        _Bxy = Move(_Map_Vec, Dir, _Bxy);
    }
    else
    {
        _Bxy = Move(_Map_Vec, Dir, _Bxy);
        _Rxy = Move(_Map_Vec, Dir, _Rxy);
    }
 
    if (Oxy == _Rxy && Oxy != _Bxy && (Ans > Count || Ans == -1))
    {
        Ans = Count;
        return;
    }
    else if (Oxy == _Bxy || Count == 10 || (Ans <= Count && Ans != -1))
        return;
 
    for (int i = 1; i <= 4; ++i)
        if(i != Dir)
            Find(_Map_Vec, i, Count + 1, _Rxy, _Bxy);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    vector<vector<char>> Map_Vec;
    pair<int, int> Rxy, Bxy;
    cin >> N >> M;
    //입력 및 구슬 위치 따로 저장.
    for (int i = 0; i < N; ++i)
    {
        Map_Vec.emplace_back();
        for (int j = 0; j < M; ++j)
        {
            char ch;
            cin >> ch;
            Map_Vec[i].emplace_back(ch);
            if (ch == 'R')
            {
                Rxy.first = i;
                Rxy.second = j;
            }
            if (ch == 'B')
            {
                Bxy.first = i;
                Bxy.second = j;
            }
            if (ch == 'O')
            {
                Oxy.first = i;
                Oxy.second = j;
            }
        }
    }
        
    Find(Map_Vec, 5, 0, Rxy, Bxy);
 
    cout << Ans;
    return 0;
}

 

잡설 :  전역변수를 평소에는 잘 안쓰는데 문제풀이 할 때만 사용해버릇 하다보니 이름 비슷한걸 차마 생각을 못하고 무지성으로 자동완성을 통해 변수명을 쓰다가 한시간 삽질 이후 함수 내부에서 _Map_Vec이 아니라 전역변수인 Map_Vec을 사용하고 있다는 것을 알았다... 하....