[Algorithm] Baekjoon 17780번 : 새로운 게임

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

17780번: 새로운 게임

#define MAX_NUM 0x3f3f3f3f
 
int dirChange(int n)
{
    switch (n)
    {
    case 1:
        return 2;
    case 2:
        return 1;
    case 3:
        return 4;
    case 4:
        return 3;
    default:
        break;
    }
}
 
struct Node
{
    deque<int> dq;
    int y;
    int x;
    int dirNum;
};
 
int board[14][14];
int pieceInfoBoard[14][14];
int dirInfo[5][2] = { {0,0}, {0,1},{0,-1},{-1,0},{1,0} };
Node pieces[11];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n, k, a, b, c;
 
    cin >> n >> k;
 
    memset(board, 0x3f, sizeof(board));
 
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= n; ++j)
        {
            cin >> board[i][j];
        }
    }
 
    for (int i = 1; i <= k; ++i)
    {
        cin >> a >> b >> c;
        pieceInfoBoard[a][b] = i;
        deque<int> dq = { i };
        pieces[i] = { dq,a,b,c};
 
    }
 
    int turnCount = 0;
    bool isBreak = false;
 
    while (1)
    {
        ++turnCount;
 
        if (turnCount > 1000)
        {
            turnCount = -1;
            break;
        }
 
        for (int i = 1; i <= k; ++i)
        {
            int curNode = i; 
 
            if (pieces[curNode].y == -100) // 다른쪽으로 합쳐짐. 
            {
                curNode = pieces[i].x; // x에 어디로 합쳐졌는지 기록해놨다.
                
                while (1) // 어디 덩어리랑 합쳐졌는지 찾아야한다.
                {
                    if (pieces[curNode].y == -100)
                    {
                        curNode = pieces[curNode].x;
                    }
                    else
                    {
                        break;
                    }
                }
            }
 
            if (pieces[curNode].dq.front() != i) // 해당 덩어리의 front가 현재 선택한 말과 일치하지않으면
            {
                continue;
            }
 
            int curY = pieces[curNode].y; // 좌표는 curNode 기준으로 (덩어리의 주인)
            int curX = pieces[curNode].x;
            int curBottom = pieces[curNode].dq.front(); // 덩어리의 맨 아래 (덩어리 주인이랑 다를 수 있음.)
 
            int nextY = curY + dirInfo[pieces[curBottom].dirNum][0]; // 맨 아래의 방향기준으로 좌표이동
            int nextX = curX + dirInfo[pieces[curBottom].dirNum][1];
 
            // 흰색칸이면
            if (board[nextY][nextX] == 0)
            {
                if (pieceInfoBoard[nextY][nextX] > 0) // 다른 말이 있다면
                {
                    int nextNode = pieceInfoBoard[nextY][nextX];
 
                    while (!pieces[curNode].dq.empty()) // 현재꺼를 다음걸로 그대로 이동.
                    {
                        int popedNode = pieces[curNode].dq.front();
                        pieces[curNode].dq.pop_front();
                        pieces[nextNode].dq.push_back(popedNode);
                    }
 
                    pieces[curNode].y = -100;
                    pieces[curNode].x = nextNode;
                    pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우기
 
                    if (pieces[nextNode].dq.size() >= 4)
                    {
                        isBreak = true;
                        break;
                    }
                }
                else // 다른 말 없으면
                {
                    pieces[curNode].y = nextY;
                    pieces[curNode].x = nextX;
                    pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
                    pieceInfoBoard[nextY][nextX] = curNode; // 다음꺼에 표시.
                }
            }
 
            // 빨간색칸이면
            else if (board[nextY][nextX] == 1) 
            {
                if (pieceInfoBoard[nextY][nextX] > 0) // 다른 말이 있다면
                {
                    int nextNode = pieceInfoBoard[nextY][nextX];
 
                    while (!pieces[curNode].dq.empty()) // 현재꺼를 다음걸로 뒤집어서 이동.
                    {
                        int popedNode = pieces[curNode].dq.back();
                        pieces[curNode].dq.pop_back();
                        pieces[nextNode].dq.push_back(popedNode);
                    }
 
                    pieces[curNode].y = -100;
                    pieces[curNode].x = nextNode;
                    pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
 
                    if (pieces[nextNode].dq.size() >= 4)
                    {
                        isBreak = true;
                        break;
                    }
                }
                else // 다른 말 없으면
                {
                    reverse(pieces[curNode].dq.begin(), pieces[curNode].dq.end());
                    
                    pieces[curNode].y = nextY;
                    pieces[curNode].x = nextX;
                    pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
                    pieceInfoBoard[nextY][nextX] = curNode; // 다음꺼에 표시.
                }
            }
 
 
            // 다음칸 파란색 or 바깥
            else if (board[nextY][nextX] == 2 || board[nextY][nextX] == MAX_NUM)
            {
                pieces[curBottom].dirNum = dirChange(pieces[curBottom].dirNum); // 일단 무조건 방향바꿔주기.
                int nextY = curY + dirInfo[pieces[curBottom].dirNum][0];
                int nextX = curX + dirInfo[pieces[curBottom].dirNum][1];
 
                if (board[nextY][nextX] == 2 || board[nextY][nextX] == MAX_NUM) // 바꾼이후 다음좌표도 파란색이거나 바깥이면
                {
                    continue; // 아무것도 하지않는다.
                }
 
                // 흰색칸이면
                if (board[nextY][nextX] == 0) 
                {
                    if (pieceInfoBoard[nextY][nextX] > 0) // 다른 말이 있다면
                    {
                        int nextNode = pieceInfoBoard[nextY][nextX];
 
                        while (!pieces[curNode].dq.empty()) // 현재꺼를 다음걸로 그대로 이동.
                        {
                            int popedNode = pieces[curNode].dq.front();
                            pieces[curNode].dq.pop_front();
                            pieces[nextNode].dq.push_back(popedNode);
                        }
 
                        pieces[curNode].y = -100;
                        pieces[curNode].x = nextNode;
                        pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우기
 
                        if (pieces[nextNode].dq.size() >= 4)
                        {
                            isBreak = true;
                            break;
                        }
                    }
                    else // 다른 말 없으면
                    {
                        pieces[curNode].y = nextY;
                        pieces[curNode].x = nextX;
                        pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
                        pieceInfoBoard[nextY][nextX] = curNode; // 다음꺼에 표시.
                    }
                }
 
                // 빨간색칸이면
                else if (board[nextY][nextX] == 1) 
                {
                    if (pieceInfoBoard[nextY][nextX] > 0) // 다른 말이 있다면
                    {
                        int nextNode = pieceInfoBoard[nextY][nextX];
 
                        while (!pieces[curNode].dq.empty()) // 현재꺼를 다음걸로 뒤집어서 이동.
                        {
                            int popedNode = pieces[curNode].dq.back();
                            pieces[curNode].dq.pop_back();
                            pieces[nextNode].dq.push_back(popedNode);
                        }
 
                        pieces[curNode].y = -100;
                        pieces[curNode].x = nextNode;
                        pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
 
                        if (pieces[nextNode].dq.size() >= 4)
                        {
                            isBreak = true;
                            break;
                        }
                    }
                    else // 다른 말 없으면
                    {
                        reverse(pieces[curNode].dq.begin(), pieces[curNode].dq.end());
 
                        pieces[curNode].y = nextY;
                        pieces[curNode].x = nextX;
                        pieceInfoBoard[curY][curX] = 0; // 현재꺼 표시 지우고
                        pieceInfoBoard[nextY][nextX] = curNode; // 다음꺼에 표시.
                    }
                }
            }
        }
 
        if (isBreak) break;
    }
 
    cout << turnCount;
}
 

 

오랜만에 풀어보는 구현문제인데 겨우 풀었다..

테스트케이스가 틀리길래 왜틀리는지 몰라서 직접 한글2018에다가 표로 각 턴마다의 이동을 그려보면서 내 코드로직 수행순서랑 비교해봤다.

그다음 테스트케이스는 다 맞길래 제출했더니 1%에서 바로 틀렸습니다가 뜨길래 다른 테스트케이스가 있는지 구글링하다가 없어서 잠시 멘붕이였다.

 

그다음 혹시 몰라서 정답이 나온 테스트케이스에 대해서 올바르게 턴이 진행되서 정답이 나오는지 체크했더니...

이동이 올바르지 않은 경우를 찾았다. 순서가 틀렸는데 우연히 정답이 맞은거였다.

해당부분 확인 후, 어디가 틀렸는지 체크하고 코드를 수정했더니 다행히 통과됐다.

N값이 작다보니 시간초과에 걸릴일은 어지간히 없다.

위의 코드같은경우도 뭔가 길고 복잡해보이지만, 수행속도는 0ms 나온다.

코드가 지저분해서 좀 모듈화시켜서 하면 깔끔하게 보이긴 하겠는데 더이상 건드리고싶지가 않아서 그냥 냅뒀다..

 

이 문제의 포인트는 합쳐지는걸 어떻게 표현하는가? 라고 생각하는데, 나같은 경우는 그냥 각 체스말마다 덱을 하나씩 할당했다. 그래서 다른 말에 합쳐진다면, 현재말에다가 '이 말은 다른 말에 의해 합쳐졌다!'라고 표시했다. 이 표시를 y값에 -100을 할당하는것으로 표시했다.  그리고 x좌표에는 어떤 말에 의해 합쳐졌는지 표시했다.

즉, 만약 1번말이 이동했더니 하얀칸이고, 하얀칸에 2번말이 있다면 2번말에 의해 합쳐진것이다.

그러면 1번노드의 y좌표에는 -100, x좌표에는 2  를 저장하는 것이다.

 

그리고 다음 턴때 해당 말을 검사할 때, '다른 말에 의해 합쳐졌다'라는 표시가 되어있다면 해당 말의 노드로 찾아간다.

해당 노드의 y값을 또 검사해본다. 왜냐하면 해당 말 또한 다른 말에의해 합쳐졌을 수 있기 때문이다.

그렇게 반복문으로 최종적으로 어떤 말에 전부 합쳐졌는지 찾는다.

어떤 말에 의해 합쳐졌는지 찾는다면 해당 말의 덱의 front를 검사해본다. (front가 맨아래에 있는 말이다)

front값이 처음 검사를 시작했던 i번째 말과 일치한다면, 그 뒤로 로직을 쭉 수행한다.

일치하지않는다면 수행하면 안된다. 왜냐하면 가장 아래에 있는 말을 기준으로 보드판을 이동하기 때문이다.