프로그래머스 - [PCCP 기출문제] 3번 / 충돌위험 찾기 C++

 이전 포스팅에 이어 2024.10.14 - [알고리즘/프로그래머스] - 프로그래머스 - [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 C++ 3번 문제를 풀어보았다. 2번 문제보다 소요시간은 1.5배 정도 걸렸는데, 해결 방법은 간단하게 생각이 되었는데, 코딩을 하는 와중에 Crash가 발생하여 시간이 오래 걸렸다. 바보 같이 for문에서 index가 아니라 count를 ++ 하면서... 문제의 난이도는 이전 문제와 비슷하게 느껴졌다.

 

알고리즘 난이도 및 시간 ( ※ 개인적인 의견 )

• 난이도 : Level 3 ( ※ Min : 0, Max : 10 )
• 풀이 시간 : 1시간 30
• 제출 횟수 : 2번 ( 코드 실수 )
• 풀이 결과 : Pass

---

문제 설명

 이번 문제는 해석하는데 큰 문제는 없었다. 오히려 내가 느끼기에는 같은 레벨이지만, 이전 문제보다 해석하기는 더 쉬웠다.  간략하게 문제를 설명하면 로봇 n대를 배달하는데 중간에 같은 칸에서 만나는 건수를 구하는 문제다. 해당 문제에서 주의해야 할 점은 r좌표가 변하는 이동을 c좌표가 변하는 이동보다 먼저 한다는 점과 보통 (x, y)를 생각하는데 r = y 고 c = x였다. 또한, 2대 이상 모인다면 충돌할 가능성이 있다는 이야기는 2대나 3대나 충돌위험이 있다고 판단하기에 동시에 2대 이상의 Case는 1건으로 본다는 점이다. 

출처 : 프로그래머스

 이번 문제 제한 사항에서는 같은 좌표에 여러 포인트가 존재하는 입력은 주어지지 않는다는 것과 같은 포인트롤 연속적으로 방문하는 입력은 주어지지 않는다는 것이다. 두 개의 문구가 왜 중요하냐면 혹시나 연속해서 같은 포인트를 이동하게 되는 경우 동일한 좌표를 계속해서 마주치게 된다. 이와 같은 경우 좌표가 같더라도 count를 해야 하기 때문에 결과 값이 달라질 수 있다. 

출처 : 프로그래머스

---

입출력

 입출력은 프로그래머스에 그림으로 예시가 너무 잘되어 있어 해당 포스팅 마지막에 있는 링크를 참조하여 이해하기 바란다.

출처 : 프로그래머스

---

문제풀이

 

 일단 첫 번째로 나는 로봇별 Route Path를 미리 다 만들어서 하는 방법을 생각했다. 딱히 복잡도도 높지 않고, O(n)만에 끝낼 수 있을 것 같기 때문에 선택하였다. 일단 Routes 개수만큼 for문을 돌게 되는데, 여기서 Key Point는 우선순위가 R이기 때문에 R 차이만큼 먼저 이동 후 C를 이동하면 된다. 그렇기 때문에 알고리즘이 어렵지는 않다. 하지만 여기서 유의해야 할 점은 차이가 -인 경우를 대비해서 ABS를 활용하여 Cycle을 돈다. 또한 첫 번째 좌표는 무조건 Insert가 필요하기 때문에 Size가 0인 경우에는 좌표를 먼저 넣어주고 시작한다.

const uint8_t MAX_ROBOT_COUNT = 101;

vector<pair<uint32_t, uint32_t>> g_RobotRouteList[MAX_ROBOT_COUNT];
//=======================================================
// @ 다음 좌표까지 이동 좌표 경로 만들기
void MakeRoutePath(const uint32_t& iRobotNum,
    const vector<int>& rCurrentPosition,
    const vector<int>& rNextPosition)
//=======================================================
{
    int iRDiff = rNextPosition[0] - rCurrentPosition[0]; // R 차이
    int iCDiff = rNextPosition[1] - rCurrentPosition[1]; // D 차이

    uint32_t iRDiffSize = abs(iRDiff); // for문 Cycle을 위해 절댓값 계산
    uint32_t iCDiffSize = abs(iCDiff);

    uint32_t iCurrRPosition = rCurrentPosition[0]; // 현재 위치를 계산하기 위험
    uint32_t iCurrCPosition = rCurrentPosition[1];

    uint32_t iTempLastRPosition = iCurrRPosition;
    if (0 == g_RobotRouteList[iRobotNum].size()) // 첫 번째 위치는 삽입하기 위함
    {
        g_RobotRouteList[iRobotNum].push_back(make_pair(rCurrentPosition[0], rCurrentPosition[1]));
    }
    for (uint32_t iRIndex = 1; iRIndex <= iRDiffSize; ++iRIndex) // 이전 좌표부터 계산하기 위해서 1부터 시작
    {
        if (0 > iRDiff) // 음수인 경우 작게 이동해야함 
        {
            g_RobotRouteList[iRobotNum].push_back(make_pair((iCurrRPosition - iRIndex), iCurrCPosition));
            iTempLastRPosition = iCurrRPosition - iRIndex;
        }
        else
        {
            g_RobotRouteList[iRobotNum].push_back(make_pair((iCurrRPosition + iRIndex), iCurrCPosition));
            iTempLastRPosition = iCurrRPosition + iRIndex;
        }
    }

    for (uint32_t iCIndex = 1; iCIndex <= iCDiffSize; ++iCIndex)
    {
        if (0 > iCDiff) // 음수인 경우 작게 이동해야함 
        {
            g_RobotRouteList[iRobotNum].push_back(make_pair(iTempLastRPosition, (iCurrCPosition - iCIndex)));
        }
        else
        {
            g_RobotRouteList[iRobotNum].push_back(make_pair(iTempLastRPosition, (iCurrCPosition + iCIndex)));
        }
    }

}

 

 그다음은 MakeRoutePath 함수를 반복해서 로봇 개수 및 방문해야 하는 경유지 개수만큼 생성하여야 하기 때문에 Control역할을 하는 함수를 하나 만들어 준다. 아래 기능은 아마 개발을 하는 사람이라면 쉽게 이해할 수 있을 것으로 예상되어 설명은 패스한다.

//=======================================================
// @ 로봇 패스 좌표를 미리 계산하기
void CalculateRobotRoute(const vector<vector<int>>& rPoints,
    const vector<vector<int>>& rRoutes)
//=======================================================
{
    uint32_t iRobotCount = static_cast<uint32_t>(rRoutes.size());
    for (uint32_t iRobotIndex = 0; iRobotIndex < iRobotCount; ++iRobotIndex)
    {
        uint32_t iRouteCount = static_cast<uint32_t>(rRoutes[iRobotIndex].size());
        g_RobotRouteList[iRobotIndex].clear();
        for (uint32_t iRouteIndex = 1; iRouteIndex < iRouteCount; ++iRouteIndex)
        {
            uint32_t current = rRoutes[iRobotIndex][iRouteIndex - 1];
            uint32_t next = rRoutes[iRobotIndex][iRouteIndex];
            MakeRoutePath(iRobotIndex, rPoints[current - 1], rPoints[next - 1]);
        }
    }
}

 

 마지막은 로봇의 경로 계획을 모두 마무리하였다면, 시간 별로 동시에 같은 칸에 마주치는 개수를 구해야 한다. 여기서 나는 좌표를 Key값으로 활용하기 위해서  map <pair <uint32_t, uint32_t>, uint32_t> m_CrossBoard라는 변수를 활용하여, 매 순간 초기화 하면서 Check를 했다. 또한 해당 칸에 방문한 Robot이 1인 경우에만 사건 발생 변수를 ++ 하면서 진행했다. 여기서 주의했던 점은 로봇마다 경로 개수가 다를 수 있기 때문에 죽을 수 있는 가능성을 줄이기 위해 로봇별로 Size를 Check 하면서 진행하였고, 모든 로봇의 경로 계획을 다 순환하는 동시에 while문을 종료하게 하였다. 

//=======================================================
// @ 마주치는 좌표 개수 구하기
int GetCrossPointCount(const uint32_t& iRobotCount)
//=======================================================
{
    int iResult = 0;
    int iCycleCount = 0;
    uint32_t iCurrentNum = 0;
    while (true)
    {
        iCycleCount = 0;
        map<pair<uint32_t, uint32_t>, uint32_t> m_CrossBoard;
        for (uint32_t iRobotIndex = 0; iRobotIndex < iRobotCount; ++iRobotIndex)
        {
            if (iCurrentNum < g_RobotRouteList[iRobotIndex].size())
            {
                if (m_CrossBoard.end() != m_CrossBoard.find(g_RobotRouteList[iRobotIndex][iCurrentNum]))
                {
                    if (1 == m_CrossBoard[g_RobotRouteList[iRobotIndex][iCurrentNum]])
                    {
                        iResult++;
                    }
                    m_CrossBoard[g_RobotRouteList[iRobotIndex][iCurrentNum]] ++;
                }
                else
                {
                    m_CrossBoard[g_RobotRouteList[iRobotIndex][iCurrentNum]] = 1;
                }
                iCycleCount++;
            }
        }
        iCurrentNum++;
        if (0 == iCycleCount) // Cycle이 0이라는 말은 이제 남은 로봇의 경로가 없기 때문에 while문을 종료한다는 의미다
        {
            break;
        }
    }
    return iResult;
}

---

결과

 다른 사람들의 풀이를 아직 보지 않았지만, dfs/bfs를 기반으로 알고리즘을 짠다면 코드가 더 간결하고 쉬웠을 것 같다. 하지만 나는 이전 포스팅에서도 언급을 했듯이 사고하는 방식이 중요하다고 생각하기 때문에 내가 생각한 방법을 논리적으로, 순서적으로 기재하여 내 코드를 누가 봤을 때 쉽게 이해할 수 있게 짜는 것이 중요하다고 생각한다. 또한, 성능에 큰 영향을 주는 것이 아니라면 공식을 외우고 문제를 풀기보다는 본인만의 방법을 찾는 것이 추후 문제를 풀 때 더 도움이 된다고 생각한다. 혹시 해당 풀이를 보고 이해가 안 가는 내용이 있다면 댓글로 남겨주기 바란다. ※ 혹시 특정 문제가 잘 안 풀려서 풀이가 필요한 경우에 댓글로 링크를 남겨주면 문제를 풀고 포스팅할 수 있도록 하겠다.

 

출처 : 프로그래머스

프로그래머스 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/340211

프로그래머스