[백준] 삼성 SW 역량 테스트 기출 - 구슬탈출2 (C언어)

https://www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

문제 해석

최대 10*10 크기인 보드가 있고, 빨간 구슬, 파란 구슬, 구슬이 통과할 수 있는 구멍이 각각 1개씩 있다.
보드를 기울임에 따라 구슬이 직선으로 움직이게 되고, 목적은 빨간 구슬을 10번 이내에 구멍을 통해 빼내는 것이다.
이 때 파란 구슬은 구멍으로 나오면 안된다.

출력은 목적을 달성하는 최소 기울임 횟수를 출력하고, 10번이 넘거나 파란구슬이 빠져나와서 불가능하게 되면 -1을 출력하는 문제다.

구슬이 움직이는 방향은 상하좌우 총 4가지 방향이고, 최대 10번의 움직임까지만 고려하면 되기 때문에 4^10 = 1048576의 경우의 수 중에서 가장 빠른 것을 출력해주면 되는 문제다.
보드가 최대 10*10 이기 때문에 한번의 기울임에 10번의 방향만 체크하면 되므로 1048576 * 10 = 10485760 의 체크가 필요하다.
상당히 큰 숫자지만 제한시간 2초 이내 풀리게 되어있다.

좀 더 깊게 생각해보면, 처음 움직임은 상하좌우 4방향이지만, 그 이후 움직임은 가장 최근의 움직임을 제외해야 한다(같은 방향으로 움직이면 구슬이 움직이지 않는다). 그리고 이전 방향과 반대 방향으로 움직이면 그 이전 구슬의 위치와 동일하게 된다(움직일 필요 X).

그래서 좀 더 정확하게 계산하면 4 * 2^9 = 2048 의 경우의 수로, 보드의 길이를 곱하면 2048 * 10 = 20480의 체크로 문제가 풀릴 수 있다.

 

풀이

큐를 이용해 구슬의 위치를 매번 기억하고, 다음 상태로 구슬의 위치를 이용할 수 있다.

index

r(x,y)

b(x,y)

count

 

• 이전의 구슬 위치를 모두 기록해 이전 구슬의 위치와 동일하면 큐에 넣지 않는다.
  
  
• 빨간 공과 파란 공은 같은 위치에 있을 수 없다.
  같은 위치일 경우 각 공의 이전 위치와 현재 위치의 거리를 계산하고, 거리가 먼 공은 한칸 덜 움직인다.

 

#include <stdio.h>
#include <queue>
#include <algorithm>
using namespace std;

struct INFO
{
    int ry, rx, bx, by, count;
};

INFO start;
char map[10][11]; // x를 11칸 잡은 이유: 문자열의 끝에 종료 문자를 저장하기 위함

int bfs()
{
    const int dy[] = {-1, 1, 0, 0};
    const int dx[] = {0, 0, -1, 1};

    int visited[10][10][10][10] = {
        0,
    };
    queue<INFO> q;
    q.push(start);
    visited[start.ry][start.rx][start.by][start.bx] = 1;

    int ret = -1;
    while (!q.empty())
    {
        INFO cur = q.front();
        q.pop();
        // 10번 초과하면 break
        if (cur.count > 10)
            break;
        // 빨간공만 구멍에 있으면 count 저장하고 break
        if (map[cur.ry][cur.rx] == 'O' && map[cur.by][cur.bx] != 'O')
        {
            ret = cur.count;
            break;
        }

        for (int dir = 0; dir < 4; ++dir)
        {
            int next_ry = cur.ry;
            int next_rx = cur.rx;
            int next_by = cur.by;
            int next_bx = cur.bx;

	  // 빨간공
            while (1)
            {
                // 현재 next의 위치가 벽도 아니고 구멍도 아니면 next의 위치 한칸 증가
                if (map[next_ry][next_rx] != '#' && map[next_ry][next_rx] != 'O')
                {
                    next_ry += dy[dir], next_rx += dx[dir];
                }
                else
                {
                    // next의 위치가 벽이라면 한 칸 빼준다
                    if (map[next_ry][next_rx] == '#')
                    {
                        next_ry -= dy[dir], next_rx -= dx[dir];
                    }
                    break;
                }
            }

	  // 파란공
            while (1)
            {
                if (map[next_by][next_bx] != '#' && map[next_by][next_bx] != 'O')
                {
                    next_by += dy[dir], next_bx += dx[dir];
                }
                else
                {
                    if (map[next_by][next_bx] == '#')
                    {
                        next_by -= dy[dir], next_bx -= dx[dir];
                    }
                    break;
                }
            }

            // 한칸에 빨간공과 파란공이 모두 존재하는 경우 예외처리
            if (next_ry == next_by && next_rx == next_bx)
            {
                // 둘 다 구멍이면 위에 빨간공만 구멍이어야 한다는 조건을 충족 못해서 count 안 세고 나감
                // 구멍이 아닐 때만 처리
                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[dir], next_rx -= dx[dir];
                    }
                    else
                    {
                        next_by -= dy[dir], next_bx -= dx[dir];
                    }
                }
            }

	  // 안 가본 곳이면 방문 처리, next 구조체에 위치 저장 후 이동횟수 증가, 큐에 next 등록
            if (visited[next_ry][next_rx][next_by][next_bx] == 0)
            {
                visited[next_ry][next_rx][next_by][next_bx] = 1;
                INFO next;
                next.ry = next_ry;
                next.rx = next_rx;
                next.by = next_by;
                next.bx = next_bx;
                next.count = cur.count + 1;
                q.push(next);
            }
        }
    }
    return ret;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", 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;

    int ret = bfs();
    printf("%d\n", ret);

    return 0;
}