Programmers - 공 이동 시뮬레이션

---

title: Programmers - 공 이동 시뮬레이션
date: 2022-09-28
tags:

• Algorithm

---

https://school.programmers.co.kr/learn/courses/30/lessons/87391

문제 요약

n x m 크기의 격자가 존재한다. 각 위치에 공이 존재하며, 이 공은 주어진 query에 맞게 움직이며 격자 바깥으로는 나가지 않는다.
모든 query 실시 후 x,y 위치에 몇 개의 공이 존재하는지 return한다.

문제 풀이

query가 200K이며, 격자의 크기는 최대 1M x 1M 이다.
격자를 하나하나 조회하는 것은 불가능하다는 의미이다.
결국 query를 기준으로 시간 측정을 해야 하며, O(n^2)는 불가능하다고 볼 수 있다.
각 query 실시에 따라 바로 공들의 위치를 판정할 수 있어야 한다.
query 실시 후 특정 사각형에 있는 공이 x,y 위치에 모이며, 이 사각형의 크기는 0일 수도 있고 매우 클 수도 있다.
이 사각형의 끝 위치를 찾는다면 문제를 해결할 수 있다.


초기 위치를 지정할 경우, Parametric Search를 이용하더라도 해결할 수 있을 것 같다.
하지만 이 경우 query를 4번 반복해야 하며, 1번만 확인하여 문제를 해결하고자 한다.
시작 위치를 알 수 없으므로, 역으로 x,y를 기준으로 사각형을 넓히는 방식으로 해결하였다.
query 실시 후 현재 위치가 되므로, query에서의 이동과 반대 방향으로 이동하면 된다.
query와 반대로 값을 증가할 때는 Max 값을 우선 이동한 후, 벽을 넘을 경우 벽에 도달한 것으로 처리한다.
이 때 Min 값이 0이라면 query의 결과 0에 모이는 공이 있다는 뜻이며, 이 때는 Min 값을 변경하지 않는다.
이외의 경우에는 모이지 않고 공이 이동만 하였다는 뜻이므로 Min 값을 증가시킨다.
만약 증가시킨 Min 값이 경계를 넘어설 경우, 해당 query를 실시할 때 현재 위치에 도달하는 공이 하나도 없다는 뜻이기에 바로 0을 return한다.
query와 반대로 값을 감소시킬 때는 반대로 적용한다. Min 값을 감소, Max값이 n-1 | m-1이라면 놔두고 아니라면 값을 감소하고, 벽을 넘어서는지 확인한다.
최종적으로 x,y에 도달하는 모든 공을 이루는 사각형의 끝 점을 알아내었기에 이 면적을 return한다.


처음에는 query를 순차적으로 탐색하는 알고리즘을 작성하였다.
Min Count와 Max Count를 1로 두고, 중간 값을 설정하였다.
벽에 부딪힐 때 Min Count 혹은 Max Count의 값을 움직이는 횟수에 따라 알맞게 증가시키고, 중간 값을 뺀다.
이렇게 최종적으로 Min과 Max의 좌표와 Count를 이용하여 x,y에 도달하는 공의 개수를 구하였다.
알고리즘에 문제가 있었는지 일부 케이스에서 실패하였으며, overflow 문제는 아니었다.
나중에 시간이 되면 다시 해당 방식으로 문제를 풀고자 한다.

프로그램

#include <vector>
#include <algorithm>

using std :: vector ;
using std :: min ;
using std :: max ;

long long solution ( int n , int m , int x , int y , vector < vector < int > > queries )
{
    long long llMaxX = x ;
    long long llMinX = x ;
    long long llMaxY = y ;
    long long llMinY = y ;
    int iQuerySize = queries.size () ;



    for ( int i = iQuerySize - 1 ; i >= 0 ; --i )
    {
        int iMoveIndex = queries [ i ] [ 0 ] ;
        int iMoveCount = queries [ i ] [ 1 ] ;


        if ( 0 == iMoveIndex )
        {
            llMaxY += iMoveCount ;

            if ( llMaxY > m - 1 )
                llMaxY = m - 1 ;
            if ( 0 != llMinY )
                llMinY += iMoveCount ;
        }
        else if ( 1 == iMoveIndex )
        {
            llMinY -= iMoveCount ;

            if ( llMinY < 0 )
                llMinY = 0 ;
            if ( llMaxY != m - 1 )
                llMaxY -= iMoveCount ;
        }
        else if ( 2 == iMoveIndex )
        {
            llMaxX += iMoveCount ;

            if ( llMaxX > n - 1 )
                llMaxX = n - 1 ;
            if ( 0 != llMinX )
                llMinX += iMoveCount ;
        }
        else if ( 3 == iMoveIndex )
        {
            llMinX -= iMoveCount ;

            if ( llMinX < 0 )
                llMinX = 0 ;
            if ( llMaxX != n - 1 )
                llMaxX -= iMoveCount ;
        }

        if ( ( llMaxX < 0 ) || ( n - 1 < llMinX ) || ( llMaxY < 0 ) || ( m - 1 < llMinY ) )
            return 0 ;
    }


    return ( llMaxX - llMinX + 1 ) * ( llMaxY - llMinY + 1 ) ;
}