[백준] 13460 구슬 탈출 2

 

 

생각하는 과정

1. R과 B가 동시에 한쪽으로 완전히 이동해야 한다.

    -> R과 B의 좌표와 기울인 횟수를 담은 Queue를 하나 만들자.

    -> 좌표의 4방향을 탐색하는 for문에서 방향 i를 공유하여 R과 B를 이동시킬 수 있을 때까지 이동시킨다. 

2. 한쪽으로 기울였을 때 R과 B가 겹치는 상황이 발생한다.

    -> R과 B가 움직인 거리를 비교해서 움직인거리가 적은 구슬의 좌표를 증가(혹은 감소)시킨다.

3. 2번을 잘 해결했다면 방문체크를 한 후에(아직 방문을 안했다면) next좌표를 push해준다. (이때 count증가)

 

이렇게 되면 R,B를 R이 0을 찾을때까지

한쪽으로 계속 기울여 가면서 최소의 count를 얻어낸다. 

 

Code

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
 
struct INFO {
    int ry, rx, by, bx, count;
};
INFO start;
 
const int MAX = 11;
char map[MAX][MAX];
const int dy[] = { -1,1,0,0 };
const int dx[] = { 0,0,-1,1 };
bool visited[MAX][MAX][MAX][MAX] = { 0, };
 
int bfs()
{
    queue<INFO> q;
    q.push(start);
    visited[start.ry][start.rx][start.by][start.bx] = 1;
 
    int result = -1;
    while (!q.empty())
    {
        INFO cur = q.front();
        q.pop();
 
        //횟수가 10초과면 그냥종료(return -1)
        if (cur.count > 10)
            break;
 
        //빨간구슬이 구멍에 들어가고 파란구슬이 구멍에 안들어갔다면 count를 리턴
        if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O')
        {
            result = cur.count;
            break;
        }
 
        //4방향 탐색
        for (int i = 0; i < 4; ++i)
        {
            //다음 위치를 일단 현재위치로 냅둔다.
            int next_ry = cur.ry;
            int next_rx = cur.rx;
            int next_by = cur.by;
            int next_bx = cur.bx;
 
            //빨간공 움직이기
            while (1)
            {
                if (map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O')
                {
                    next_ry += dy[i], next_rx += dx[i];
                }
                else
                {
                    if (map[next_ry][next_rx] == '#')
                    {
                        next_ry -= dy[i], next_rx -= dx[i];
                    }
                    break;
                }
 
            }
            //파란공 움직이기
            while (1)
            {
                if (map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O')
                {
                    next_by += dy[i], next_bx += dx[i];
                }
                else
                {
                    if (map[next_by][next_bx] == '#')
                    {
                        next_by -= dy[i], next_bx -= dx[i];
                    }
                    break;
                }
            }
            //빨간공과 파란공의 위치가 같으면 더 많이 움직인 쪽에서 움직인 방향만큼 뺴줘야한다.
            if (next_ry == next_by && next_rx == next_bx)
            {
                if (map[next_ry][next_rx] != 'O')
                {
                    int red_dist = abs(next_ry - cur.ry) + abs(next_rx - cur.rx);
                    int blue_dist = abs(next_by - cur.by) + abs(next_bx - cur.bx);
 
                    if (red_dist > blue_dist)
                    {
                        next_ry -= dy[i], next_rx -= dx[i];
                    }
                    else
                    {
                        next_by -= dy[i], next_bx -= dx[i];
                    }
                }
            }
            //방문체크 후에 push
            if (visited[next_ry][next_rx][next_by][next_bx] == 0)
            {
                visited[next_ry][next_rx][next_by][next_bx] = 1;
                q.push({ next_ry, next_rx, next_by, next_bx, cur.count + 1 });
            }
        }
    }
    return result;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        cin >> map[i];
 
    for (int y = 0; y < n; ++y) 
    {
        for (int x = 0; x < m; ++x)
        {
            if (map[y][x] == 'R') 
            {
                start.ry = y, start.rx = x;
            }
            if (map[y][x] == 'B') {
                start.by = y, start.bx = x;
            }
        }
    }
 
    start.count = 0;
    cout << bfs();
 
    return 0;
}
 
 

 

자세한 풀이는 해당 유튜브를 참고했다. https://www.youtube.com/watch?v=SarTy3ZwmVo