[Algorithm] Baekjoon 13460번 : 구슬 탈출 2

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

13460번: 구슬 탈출 2

struct Node
{
    int y;
    int x;
    int index;
    int count;
};
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
bool visited[11][11][11][11] = { 0 };
 
int row, col;
char colors[2] = { 'R','B' };
char arr[11][11];
char tempArr[11][11];
Node nodes[2];
 
int GetFirstIndex(int dir)
{
    switch (dir)
    {
    case 0:return nodes[0].y < nodes[1].y ? 0 : 1;
    case 1:return nodes[0].y > nodes[1].y ? 0 : 1;
    case 2:return nodes[0].x < nodes[1].x ? 0 : 1;
    case 3:return nodes[0].x > nodes[1].x ? 0 : 1;
    default:return -1;
    }
}
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> row >> col;
 
    for (int i = 0; i < row; ++i)
    {
        for (int j = 0; j < col; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 'R') nodes[0] = { i,j,0,0 };
            if (arr[i][j] == 'B') nodes[1] = { i,j,1,0 };
        }
    }
    
    arr[nodes[0].y][nodes[0].x] = '.';
    arr[nodes[1].y][nodes[1].x] = '.';
 
    visited[nodes[0].y][nodes[0].x][nodes[1].y][nodes[1].x] = true;
 
    queue<Node> q;
    q.push(nodes[0]);
    q.push(nodes[1]);
 
    while (!q.empty())
    {
        Node first = q.front();
        q.pop();
        Node second = q.front();
        q.pop();
 
        if (first.count == 10)
        {
            continue;
        }
 
        if (first.index == 0)
        {
            nodes[0] = first;
            nodes[1] = second;
        }
        else
        {
            nodes[0] = second;
            nodes[1] = first;
        }
 
        for (int i = 0; i < 4; ++i) // 각 방향, 여기서마다 원본으로 해야됨.
        {
            memcpy(tempArr, arr, sizeof(arr));
            tempArr[first.y][first.x] = colors[first.index];
            tempArr[second.y][second.x] = colors[second.index];
 
            vector<Node> tempNodes(2);
            vector<int> indices;
            bool isRed = false;
            bool isBlue = false;
            int firstIndex = GetFirstIndex(i);
 
            indices = { firstIndex, !firstIndex };
 
            for (int j = 0; j < 2; ++j) // 우선순위에 따라 빨,파 혹은 파,빨.
            {
                int standardY = nodes[indices[j]].y;
                int standardX = nodes[indices[j]].x;
 
                while (1) // 
                {
                    int nextY = standardY + dir[i][0];
                    int nextX = standardX + dir[i][1];
 
                    if (tempArr[nextY][nextX] == '#' || tempArr[nextY][nextX] == 'R' || tempArr[nextY][nextX] == 'B') // 다음게 벽, 즉 멈춰야 할 위치.
                    {
                        tempArr[nodes[indices[j]].y][nodes[indices[j]].x] = '.';
                        tempArr[standardY][standardX] = colors[indices[j]];
                        break;
                    }
                    else if (tempArr[nextY][nextX] == 'O')
                    {
                        tempArr[nodes[indices[j]].y][nodes[indices[j]].x] = '.';
 
                        if (indices[j] == 0) isRed = true;
                        else isBlue = true;
                        break;
                    }
                    else
                    {
                        standardY = nextY;
                        standardX = nextX;
                    }
                }
 
                tempNodes[indices[j]] = { standardY,standardX }; 
            }
 
            if (isBlue) continue;
            if (isRed)
            {
                cout << nodes[0].count + 1;
                return 0;
            }
 
            if (visited[tempNodes[0].y][tempNodes[0].x][tempNodes[1].y][tempNodes[1].x]) continue;
            else
            {
                visited[tempNodes[0].y][tempNodes[0].x][tempNodes[1].y][tempNodes[1].x] = true;
 
                q.push({ tempNodes[0].y, tempNodes[0].x, 0, nodes[0].count + 1 });
                q.push({ tempNodes[1].y, tempNodes[1].x, 1, nodes[0].count + 1 });
            }
        }
    }
 
    cout << -1;
 
    return 0;
}

저번에 플레문제 이후로 나를 오래 괴롭힌 문제이다.

일단 문제조건을 잘못 이해했다는게 가장 크다...

프로그래머스에서 풀었던 리코쳇로봇처럼 끝까지 간다음에 해당위치가 구멍이면 빠지는 식인줄 알았다.

하지만 그냥 경로에 구멍이 있으면 바로 빠지는 문제이다. 테스트케이스를 너무 대충 훑어봤던것 같다.

 

로직은 대략 아래와 같다.

시작위치를 기준으로 상,하,좌,우로 전부 기울여본다(즉 공을 굴려본다).

공을 굴리기 전에 어떤공을 먼저 굴려야하는지 반드시 체크해야 한다. 다른사람들 풀이에는 그냥 먼저 굴린다음 겹쳤을 때 체크하는데, 나는 그냥 처음부터 어떤공을 굴릴지 체크하는게 마음이 편해서(?) 이런식으로 했다.

GetFirstIndex가 해당되는 함수이고, 빨간공과 파란공의 위치를 비교해서 각각의 방향에 따라 어떤걸 먼저 굴릴지 구했다.

 

굴리다가 멈춰야 한다면(벽이거나 자신과 다른색깔의 공), 처음위치와 값을 바꿔준다음 ('R'과 '.') 반복문을 탈출하고 다음공을 굴린다. 바꿔줘야하는걸 까먹지 말자. 안그러면 다음공이 굴러가지 못한다.

 

굴리다가 구멍을 만나면 시작위치를 '.'으로 바꿔주고 현재 구멍에 어떤 색깔의 공이 빠졌는지 체크해준다.

 

이후 해당방향으로 두개의 공을 굴렸다면, 구멍에 어떤 공이 빠졌는지에 따라 진행한다(경로에 구멍이 있었다면)

파란공이 빠졌다면, 큐에 노드를 넣지않고 바로 다음 반복문(다음 방향)을 진행한다.

빨간공이 빠졌더라도 파란공이 빠져있으면 실패한걸로 간주하기 때문이다.

그렇기 때문에 모든 경우에서 파란공이 빠져있다면 그냥 무시한다.

 

파란공이 안빠진 상태에서 빨간공이 빠졌다면 바로 로직을 종료하면 된다.

파란공이 안빠진 상태에서 빨간공도 안빠졌다면 방문체크를 하고 비로소 큐에 노드를 넣으면 된다.

 

그리고 방문체크는 4차원으로 한다. 즉 빨간공위치,파란공위치좌표로 방문체크를 하는것이다.

처음에 단순히 visited[2][11][11]로 했다가 제대로 방문체크가 안되는 현상을 확인할 수 있었다.

이것은 독립적인 방문체크가 안되기 때문이다.

이 문제에서의 확실한 중복은, '공을 굴리기 전'에 특정좌표들 각각 있었는지이다. (표현을 뭐라해야할지 모르겠다)

두 공은 반드시 같은방향으로 같이 움직이기 때문이다.