[ 프로그래머스 방의 개수 (Lv5) ] (C++)

프로그래머스의 방의 갯수(Lv5) 문제이다.

[ 문제풀이 ]

주어진 방향대로 선을 그었을 때, 만들어 진 방의 갯수를 return 해야 하는 문제이다.

생각보다 문제가 단순해 보이지만, 보이지 않는 함정 같은 요소들이 숨어있으니 천천히 알아보도록 하자.

먼저, '방'을 이루기 위해서는 어떤 조건이 필요한지부터 정답을 도출하는 과정까지 진행해보자.

#1. 방 만들기

먼저 주어진 방향대로 선분을 그었을 때, '방'을 이루기 위해서는 어떤 조건이 필요한지 생각을 한번 해보자.

.

위와 같은 맵이 존재한다고 가정해보자. 시작점 (0, 0)은 위의 그림에서 파랑색으로 표시된 동그라미라고 가정하자.

이 때, 이동하는 방향이 [ 2 , 5 , 0 ] 으로 주어졌다고 가정해보자.

순차적으로 선을 그어보면 다음과 같은 모양이 만들어진다.

.

그럼 위와 같은 주황색 삼각형이 하나 만들어진다. 즉 ! [ 2 , 5 , 0 ] 을 통해서 우리는 방이 1개 있음을 구할 수가 있다.

이 때, 방이 1개가 있다는 것을 어떻게 판단해 줄 수 있을까 ??

바로, "방문했던 정점을 다시한번 재방문 하는 경우" 방이 생성되는 것을 알 수 있다.

파랑색으로 표시된 동그라미를 한번 보자. 처음에 방향 '2'로 움직이는 과정에서 파랑색 동그라미는 이미 한번 방문했다고 표시가 될 것이다. 그 후에, 마지막 방향 '0'으로 움직이는 과정에서 파랑색 동그라미는 2번째 방문을 하게 된다.

즉 ! 방문했던 정점을 다시한번 방문하는 경우, 방이 생성된다는 것을 알 수 있다.

하지만 다음과 같은 경우를 한번 생각해보자.

이동하는 방향이 [ 2 , 6 ] 으로 주어졌다고 가정해보자.

.

마찬가지로 하늘색 동그라미에서 시작한다고 가정한다면, 방향 '2'를 통해서 우측으로 한칸 이동 후, '6'을 통해서 다시 하늘색 정점으로 돌아오게 될 것이다.

이 때 방이 만들어 졌을까 ?? 만들어 지지 않았다. 따라서, 우리가 위에서 이야기 했던 대로, "방문했던 정점을 재방문" 했으므로 방이 하나 만들어졌다고 판단을 하면 안 되는 것이다.

그럼 어떤 조건이 더 추가되어야 할까 ???

바로, "현재 만들어 지는 간선이 기존에 만들어진 적 없으면서, 하나의 정점을 재방문하는 경우" 방이 만들어 진다고 판단할 수 있다.

.

다시 이 상황을 보자. 하늘색 정점을 (0 , 0)으로 가정하고, 하늘색 정점의 오른쪽에 있는 정점을 (0 , 1)이라고 표현해보자.

방향 '2'에 의해서 (0 , 0)과 (0 , 1)을 연결하는 간선은 한 번 만들어 지게 된다. 이 때, 이 간선은 방향성이 없으므로

(0 , 1)과 (0 , 0)을 연결하는 간선이 만들어 졌다고 가정해도 무방하다.

이 상태에서 방향 '6'을 진행해보자. (0 , 1)에서 (0 , 0)으로 가는 간선이 그어질 것인데, 이 간선은 이미 기존에 만들어 진 적이 있는 간선이다. 즉 ! (0 , 0)이라는 정점을 재방문 함에도 불구하고, '6'에 의한 간선은 기존에 이미 만들어진 적 있는 간선이기 때문에 이 경우에는 방이 생성되지 않는다는 것이다.

.

이 경우를 다시한번 보자. (0 , 0)에서 방향 '2'에 의해서 (0 , 1)을 잇는 간선이 하나 발생할 것이다.

- 방향 '2'에 의해서 (0 , 0) 과 (0 , 1)을 혹은 (0 , 1)과 (0 , 0)을 잇는 간선이 생성.

방향 '5'에 의해서 (0 , 1)과 (1 , 0)을 잇는 간선이 하나 발생할 것이다.

이 때까지만 하더라도 ,방문한 정점에 대한 재방문이 없기 때문에 방이 생겼다고 판단되지는 않을 것이다.

- 방향 '5'에 의해서 (0 , 1)과 (1 , 0)을 혹은 (1 , 0)과 (0 , 1)을 잇는 간선이 생성.

마지막 방향 '0'에 의해서 (1 , 0)과 (0 , 0)을 잇는 간선이 하나 발생할 것이다.

이 경우 ! (0 , 0)이라는 정점이 2번째 방문하게 된다. 왜 ?? (0 , 0)은 이미 가장 처음에 한번 방문을 한 정점이기 때문이다.

그런데 (1 , 0)과 (0 , 0)을 잇는 간선 혹은 (0 , 0)과 (1 , 0)을 잇는 간선은 기존에 연결된 적이 없었던 간선이다.

즉 ! 이 경우에는 방이 생성된다고 판단할 수 있다.

따라서 다음과 같이 정리해볼 수 있다.

- 방이 생성되는 경우

1. 1차적으로 기존에 방문한 정점을 재 방문하는 경우 방이 생성될 가능성이 있다.

2. 1의 조건을 만족하면서, 동시에 해당 간선이 기존에 만들어 진 적 없는 간선이라면 방이 만들어 진다.

#2 정점 및 간선의 관리

#1의 내용을 통해서 우리는 언제 방이 생성되는지 아닌지를 판단하기 위해서는 정점과 간선에 대한 방문에 대한 처리가 필요하다. 이 처리만 한다면 정답은 쉽게 구할 수 있을 것이다.

그래서 본인은 map을 이용해서 정점과 간선을 관리해 주었다.

처음에는 단순하게, 정점에 대해서는 2차원 배열을, 간선에 대해서는 4차원 배열을 관리해 보려고 하였다.

예를 들어서 Node_Visit[a][b] = true 라는 것은, (a , b)라는 정점은 기존에 방문한 적이 있습니다. 혹은

Edge_Visit[a][b][c][d] = true 라는 것은, (a , b)와 (c , d)를 잇는 간선은 기존에 만들어 진 적이 있습니다. 이런식으로 관리를

해보려고 했으나, 이렇게 했을 때의 문제가 있다.

바로, "음수 영역에 대한 처리가 불가능" 하다는 것이다. 왜 그럴까 ?? 배열의 인덱스에는 음수의 값이 들어갈 수가 없다.

하지만, 이 문제 같은 경우 음수 좌표들에도 자유자재로 계산이 가능해야 한다.

왜 그럴까 ?? 시작점은 (0 , 0)이라고 주어졌지만, 만약 주어진 방향이 '6'이 주어진다면 (0 , 0)에서 왼쪽으로 한칸 움직인

(0 , -1)에 대해서 계산을 할 수 있어야 하기 떄문이다. 즉 ! 이런 부분 때문에 단순히 2차원 혹은 4차원 배열로는 관리가

힘든 부분이 존재한다.

따라서 본인은 맵으로 정점의 좌표들과 간선의 좌표들을 관리해 주었다.

map은 [ Key , Value ] 를 한 쌍으로 관리할 수 있는 자료구조이다. 즉 ! 해당 Key값이 어떤 Value를 가지고 있는지에 대해서 쉽게 관리할 수 있는 자료구조이다.

정점을 관리하는 map에 대해서는 이 Key값을 pair로 만들어 주었다. 왜냐하면 하나의 정점은 x좌표, y좌표가 쌍으로 존재하기 때문이다. 따라서, map<pair<int, int>, bool> Node_Visit 이런 형태로 map을 선언 후, 정점들을 관리해 주었다.

간선을 관리하는 map에 대해서는 이 Key값을 2개의 페어를 한번에 관리하도록 만들어 주었다.

왜냐하면, 하나의 간선은 2개의 정점을 연결하는 것이고, 이 정점들은 각각의 x좌표와 y좌표가 쌍으로 존재하기 때문에,

간선이 잇는 2개의 정점에 대한 { x , y } 를 한번에 관리해 주었다.

따라서, map<pair<pair<int, int>, pair<int, int>> , bool> Edge_visit 이런 형태로 map을 선언 후, 간선들을 관리해 주었다.

정점 관리를 위한 map : map< pair<int , int> , bool > Node_Visit

간선 관리를 위한 map : map< pair<pair<int, int> , pair<int, int>> , bool > Edge_Visit

#3. 함정 : 예외 Case

위의 #1과 #2를 통해서 정답을 굉장히 수월하게 구할 수 있을 것 같지만, 사실은 그렇지 않다.

.

위의 상황을 한번 보자. 하늘색 정점이 (0 , 0)이다. 이 때, 방향이 [ 2 , 5 , 2 , 7 ] 로 주어졌다고 가정해보자.

그럼 순서대로 한번 간선을 그려보면 다음과 같은 그림이 완성된다.

.

방이 몇개가 있을까 ?? 딱 봐도 '2'개가 있다는 것을 알 수 있다.

하지만 ! 우리가 위에서 구한대로 계산을 한다면, 아마 방이 '1'개가 있다는 결론이 날 것이다.

왜 그럴까 ?? 한번 하나하나 진행해보자.

0. 초기화

- (0 , 0)의 정점을 방문했다고 표시해준다.

  방문한 정점 : [ (0 , 0) ]

1. 방향 '2'

- (0 , 0)에서 (0 , 1)을 잇는 간선이 생성된다. 동시에 (0 , 1)이 방문한 정점에 포함되어진다.

  방문한 정점 : [ (0 , 0) , (0 , 1) ]

  만들어진 간선 : [ { (0 , 0) & (0 , 1) } ]

(실제로 간선은 (0 , 0)과 (0 , 1)을 잇는 간선, (0 , 1)과 (0 , 0)을 잇는 간선이 모두 생성되었다고 표현해야 하지만,.

 편의상 하나만 표시하도록 하겠습니다.)

2. 방향 '5'

- (0 , 1)에서 (1 , 0)을 잇는 간선이 생성된다. 동시에 (1 , 0)이 방문한 정점에 포함되어 진다.

  방문한 정점 : [ (0 , 0) , (0 , 1) , (1 , 0) ]

  만들어진 간선 : [ { (0 , 0) & (0 , 1) } , { (0 , 1) & (1 , 0) } ]

3. 방향 '2'

- (1 , 0)에서 (1 , 1)을 잇는 간선이 생성된다. 동시에 (1 , 1)이 방문한 정점에 포함되어 진다.

  방문한 정점 : [ (0 , 0) , (0 , 1) , (1 , 0) , (1 , 1) ]

  만들어진 간선 : [ { (0 , 0) & (0 , 1) } , { (0 , 1) & (1 , 0) } , { (1 , 0) & (1 , 1) } ]

4. 방향 '7'

- (1 , 1)에서 (0 , 0)을 잇는 간선이 생성된다. 이 떄, (0 , 0)은 이미 방문한 정점이기 때문에 재방문이 일어나게 된다.

  동시에 ! (1 , 1)과 (0 , 0)을 잇는 간선은 기존에 만들어진 적 없는 간선이기 때문에 이 때 방의 갯수가 1개 추가되어진다.

결과적으로 방의 갯수는 '1개' 가 된다.

왜 이런 현상이 발생하는 것일까 ?? 실제로는 방의 갯수가 2개이지만 왜 방의 갯수가 1개가 되는 것일까 ??

바로 "표시되어 질 수 없는 정점 때문" 에 이런 현상이 발생하게 된다. 다시한번 그림을 봐보자.

.

위의 그림에서 본인이 하나의 정점을 임의로 그려넣어보겠다.

.

초록색 정점을 한번 주목해보자. 초록색 정점은 과연 몇 번 방문이 일어나게 될까 ??

.

(색깔이 표시가 잘 안나서 간선들의 색깔을 조금 바꿨습니다)

초록색 정점 같은 경우에는 총 2번 방문하게 된다.

(0 , 1)에서 (1 , 0)으로 가는 방향 '5'에 의해서 생기는 간선이 생길 때, 한번 방문하게 되고, (파랑색 간선)

(1 , 1)에서 (0 , 0)으로 가는 방향 '7'에 의해서 생기는 간선이 생길 때, 또 한번 방문하게 된다. (빨강색 간선)

즉 ! 이렇게 총 2번을 방문하게 된다. 결과적으로 초록색 정점에서도 방의 갯수가 하나 추가되어야 한다는 것이다.

그래서, 이 문제의 정답은 (0 , 0)에서 방의 갯수가 하나 추가되어지고, 초록색 정점에서 방의 갯수가 하나 추가되어져서 총 2개의 방의 갯수가 있게 되는 것이다.

하지만 ! 초록색 정점은 언제까지나 본인이 표시한 정점일 뿐, 실제로는 계산이 되질 않는다.

왜 ?? 정수에 해당하는 좌표에 있는 정점이 아니기 때문이다.

하늘색 정점이 (0 , 0)이라고 했으니 초록색 정점에 굳이 좌표를 한번 매겨보자면 (0.5 , 0.5) 정도 될 것이다.

그런데 ! 우리가 (0.5 , 0.5)를 계산할 수 있을까 ?? 뭐 굳이 하려고 애를 쓴다면 할 수는 있을 것이다.

우리가 위에서 선언해놓은 map으로 관리를 한다고 했을 때, double형으로 자료형들을 선언해주고, 어찌저찌 한다면 뭐 할 수는 있을 것이다. 그런데 굉장히 복잡해질 것이다.

따라서 ! 본인은 아예 2칸씩 움직여 주었다. 무슨말일까 ??

주어진 명령어 [ 2 , 5 , 2 , 7 ] 을 2칸씩 움직이는 형태로 다시한번 표시해 보겠다.

그럼 다음과 같이 간선이 만들어 진다는 것을 확인할 수 있다.

.

2칸씩 움직였을 때의 결과물이다. 과연 이 경우에는 정답이 몇개가 나올까 ?? 정확하게 2개가 나올 것이다.

왜 ? (0 , 0)에서 1개, (1 , 1)에서 1개. 이렇게 총 2개의 방이 생성된다는 결과를 낼 수 있을 것이다.

따라서 ! 문제에서 주어진 대로 한칸씩만 움직이면서 간선을 그렸을 때에는, 중간중간 표시되지 않는 정점들에 의해서 방의 갯수가 제대로 구해지지 않는 경우가 발생되어 진다.

따라서, 위와 같이 모든 방향의 움직임들에 대해서 모두 2번씩 실행되어진다면, 그런 표시되지 않는 정점들 또한 모두 정수로 표시되는 정점들 만으로도 계산이 가능하다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <map>
 
using namespace std;
 
int dx[] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
 
int solution(vector<int> arrows) 
{
    map<pair<int, int>, bool> Node_Visit;
    map<pair<pair<int, int>, pair<int, int>>, bool> Edge_Visit;
    
    int answer = 0;
    int x = 0;
    int y = 0;
    Node_Visit[{x, y}] = true;
    for (int i = 0; i < arrows.size(); i++)
    {
        int dir = arrows[i];
        for (int j = 0; j < 2; j++)
        {
            int nx = x + dx[dir];
            int ny = y + dy[dir];
 
            if (Node_Visit[{nx, ny}] == true && Edge_Visit[{ {x, y}, { nx, ny }}] == false)
            {
                Edge_Visit[{ {x, y}, { nx, ny }}] = true;
                Edge_Visit[{ {nx, ny}, { x, y }}] = true;
                answer++;
                x = nx;
                y = ny;
                continue;
            }
 
            Node_Visit[{nx, ny}] = true;
            Edge_Visit[{ {x, y}, { nx, ny }}] = true;
            Edge_Visit[{ {nx, ny}, { x, y }}] = true;
            x = nx;
            y = ny;
        }
    }
    return answer;
}