Programmers - 2차원 동전 뒤집기

---

title: Programmers - 2차원 동전 뒤집기
date: 2022-10-28
tags:

• Algorithm
• Greedy

---

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

문제 요약

2차원의 직사각형 체스판이 주어지며, 각 칸은 앞면과 뒷면이 다른 동전으로 채워져있다.
열 혹은 행 단위로 뒤집을 수 있을 때, 주어진 동전을 뒤집어 목표 상태를 만들어야 한다.
만들 수 있을 때 최소 뒤집는 횟수를, 못 만들면 -1을 return한다.

문제 풀이

처음에 문제를 봤을 때는 Brute Force 혹은 DFS 등의 방식으로 풀어야 하는줄 알았다.
하지만 각 Row와 Column을 기준으로 뒤집는다는 것에서 풀이 방안을 쉽게 떠올릴 수 있었다.
0과 1의 신호로 바꾸고, 각 Line 단위로 신호를 흘려 0과 1을 바꾸는 것으로 인식하면 쉽다.


같은 Line을 두 번 뒤집으면 초기 상태가 된다.
결국 각 Row와 Column은 최대 1번만 뒤집는다.
(i,j) 위치가 목표와 같다면 ith Row, jth Column 모두 뒤집었을 수도 있고, 안 뒤집었을 수도 있다.
이를 동시에 생각하면 귀찮다. 그냥 앞에서 Greedy하게 확인하면 된다.
처음에는 0번 Row를 기준으로, 목표와 다르면 해당 Column을 뒤집었다.
목표 상태를 만들 수 있다면, 어느 Column을 조회해도 목표와 다른 Row가 동일할 것이다.
그냥 0번 Column 기준으로 비교하며 다르면 Row를 뒤집는다.
뒤집은 이후에는 전체를 비교하여 목표와 다른지 확인하면 된다.
목표와 같을 경우, 전체 Row와 Column의 개수 - Count 개수와 현재 Count 개수 중 더 작은 것이 답이다.
이러면 전체 0과 1이 바뀌어 목표와 정반대라고 착각할 수 있으나, 전체 Row와 Column을 기준으로 한 번 더 뒤집은 후, 2번 뒤집은 것은 안 뒤집은 것으로 인식하는 것과 동일하다.


개별 상태를 비교하는 것에 초점을 맞춘 문제이나, 결국 Row 혹은 Column이라는 큰 단위로 묶여있다는 것을 눈치채면 좋은 성능으로 문제를 해결할 수 있다.

프로그램

#include <vector>
#include <queue>

using std :: vector ;
using std :: queue ;

vector < int > solution ( int n , vector < vector < int > > roads , vector < int > sources , int destination )
{
    vector < int > answer ;
    vector < vector < int > > vPath ( n ) ;
    vector < int > vDest ( n , 1e5 ) ;
    int iRoadSize = roads.size () ;
    queue < int > qNode ;



    for ( int i = 0 ; i < iRoadSize ; ++i )
    {
        vPath [ roads [ i ] [ 0 ] - 1 ].emplace_back ( roads [ i ] [ 1 ] - 1 ) ;
        vPath [ roads [ i ] [ 1 ] - 1 ].emplace_back ( roads [ i ] [ 0 ] - 1 ) ;
    }

    qNode.emplace ( -- destination ) ;
    vDest [ destination ] = 0 ;

    while ( ! qNode.empty () )
    {
        int iNode = qNode.front () ;
        int iLength = vDest [ iNode ] ;
        qNode.pop () ;

        for ( int iTempDest : vPath [ iNode ] )
        {
            if ( 1e5 != vDest [ iTempDest ] )
                continue ;

            if ( iLength + 1 < vDest [ iTempDest ] )
            {
                vDest [ iTempDest ] = iLength + 1 ;
                qNode.emplace ( iTempDest ) ;
            }
        }
    }

    for ( int i : sources )
    {
        --i ;

        int iLength = vDest [ i ] ;

        if ( 1e5 <= iLength )
            iLength = -1 ;

        answer.emplace_back ( iLength ) ;
    }


    return answer ;
}