구슬 탈출2

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#define ll long long
using namespace std;
int N,M,cnt;
char board[15][15];
bool vis[15][15];
pair<int,int> Red;
pair<int,int> Blue;
pair<int,int> hole;
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
int arr[15];
bool flag = false;
vector<int> ans;
void DFS(int ry, int rx, int by, int bx,  int depth, int dir)
{
    if(depth > 10) return;

    int ny = ry + dy[dir];
    int nx = rx + dx[dir];
    int nny = by + dy[dir];
    int nnx = bx + dx[dir];
    bool fR = false;
    bool fB = false;
    if(nx<0 or ny<0 or nx>=M or ny>=N) return;
    // Red 이동
    while(board[ny][nx] != '#')
    {
        if(ny == hole.first and nx == hole.second)
        {
            // 종료
            fR = true;
            ny = -1;
            nx = -1;
            goto Blue;
        }
        ny += dy[dir];
        nx += dx[dir];
    }
    ny -= dy[dir];
    nx -= dx[dir];

    Blue :;
    // Blue 이동
    while(board[nny][nnx] != '#')
    {
        if(nny == hole.first and nnx == hole.second)
        {
            // 종료
            fB = true;
            goto stop;
        }
        nny += dy[dir];
        nnx += dx[dir];
    }
    nny -= dy[dir];
    nnx -= dx[dir];

    // 두개의 좌표가 같다면 원래 위치와 방향을 고려해서 값 조정
    if(ny == nny and nx == nnx){
        if(dir == 0){
            if(ry < by) ny--;
            else nny--;
        }else if(dir == 1){
            if(rx < bx) nx--;
            else nnx--;

        }else if(dir == 2){
            if(ry < by) nny++;
            else ny++;

        }else if(dir == 3){
            if(rx < bx) nnx++;
            else nx++;
        }
    }

    stop:;
    if(fB) return;
    else if(!fB and fR)
    {
        ans.push_back(depth);
        return;
    }
    /* 다른 방향에 대해서 DFS 수행 */
    for(int d=0;d<4;d++)
        if(dir != d)
            DFS(ny, nx, nny, nnx, depth+1, d);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'R')
                Red = {i,j};
            else if(board[i][j] == 'B')
                Blue = {i,j};
            else if(board[i][j] == 'O')
                hole = {i,j};
        }
    for(int dir=0;dir<4;dir++)
        DFS(Red.first, Red.second, Blue.first, Blue.second, 1, dir);
    sort(ans.begin(), ans.end());
    if(ans.empty())
        cout << -1;
    else 
        cout << ans.front();
    return 0;
}

• 로직
  • 'R' / 'B' / 'O' 각각 좌표에 저장
  • 4방향에 대해서 DFS 수행
    • Red 이동
    • Blue 이동
    • 두개의 좌표가 겹친다면 최초 좌표와 방향을 고려해서 조정! (매우 중요!)
    • Red만 hole에 들어갔는지 검사
    • 4방향에 대해서 DFS 다시 수행
  • ans 오름차순 정렬
  • 정답 추출

• 느낀 점
  • 로직 수행 후 4방향에 대해 DFS를 수행하는 코드 방식은 반드시 모든 방향에 대해 수행함
    (반복문 내부에 continue로 dir 증가해서 수행했을때 dir이 0,1,2만 나왔었음 --> 주의)