[프로그래머스/C++] 방의 개수

 

 

문제

문제 설명

 

 

 

풀이

 

[문제 풀이]

 

이 문제는 닫힌 도형이 몇개가 되는지 구하면 되는 문제다.

 

쉽게 생각하면 닫힌 도형이란 이미 방문한 노드를 다시 방문할 경우 닫히게 된다.

그림을 보면 더 쉽게 이해가 된다.

위 그림처럼 C에서 A방향으로 이동하고, 그 뒤 이미 방문한 노드인 A를 방문하면 닫힌 도형이 만들어지게 된다. 

 

여기서 중요한 점은 이미 방문한 노드를 방문한다고 해서 무조건 닫힌 도형이 되는 것은 아니라는 점이다.

 

아래 그림에서 이미 A와 B라는 점을 방문했다고 가정하자.

이 경우 A에서 이전에 방문한 노드인 B를 방문하거나 B에서 이미 방문한 A를 방문하더라도 닫힌 도형이 새로 만들어지지 않는다. 

 

그렇기 때문에 Set으로 A에서 B로 가는 간선을 방문했는지 파악하고 이미 간선을 방문했다면, 닫힌 도형이 만들어지지 않으므로 개수에 포함시키지 않으면 된다.

 

위 과정을 반복해 Set으로 중복을 제거하고 몇개의 방(닫힌 도형의 개수)이 만들어지는지 return했다.

 

+ [0,3,0,5] 방향으로 이동할 경우 방이 2개 만들어지게 된다. 여기서 대각선으로 교차되지만, 교차되는 부분이 노드에 포함되지 않아 방의 개수를 세는데 어려움이 있다. 그래서 이 문제를 해결하기 위해 [0,3,0,5]를 [0,0,3,3,0,0,5,5]로 변환해 문제를 풀면 대각선 노드가 생겨 쉽게 문제를 풀 수 있다.

 

[아이디어 정리]

1. Set을 이용해 이미 방문한 노드들을 파악한다.
2. Set을 이용해 특정 노드에서 특정 노드에 도달하는 간선들을 파악한다.
3. 특정 점에서 한번도 이용하지 않은 간선을 통해 이미 방문한 노드를 방문한다면, 닫힌 도형이 만들어지므로 개수에 추가한다.
4. 닫힌 도형의 개수를 return한다.

[아이디어 정리2]

1. Set을 이용해 이미 방문한 노드들을 파악한다.
2. Set을 이용해 특정 노드에서 특정 노드에 도달하는 간선들을 파악한다.
3. 도형이 만들어질 때 마다 노드의 개수와 간선의 개수가 1개씩 차이가 나게 된다.
4. Set으로 중복된 노드와 간선들을 전부 제거한 다음, 간선의 개수-노드의 개수 +1 을 return 한다.

아이디어2는 삼각형이 만들어 질 때, 이미 방문한 노드를 방문하므로 Set에 노드는 추가되지 않고 간선은 추가가 된다. 이처럼 닫힌 도형이 만들어 질 때마다 노드의 개수와 간선의 개수가 1씩 차이나므로 이를 이용해 Set의 개수로 쉽게 구할 수 있다.

 

 

Code

 

 

#include <string>
#include <vector>
#include <set>
using namespace std;
int dy[8]={1,1,0,-1,-1,-1,0,1};
int dx[8]={0,1,1,1,0,-1,-1,-1};

int solution(vector<int> arrows) {
    int answer = 0, ny=0,nx=0;
    set<pair<int,int>> yxSet;
    set<pair<pair<int,int>,pair<int,int>>> dirSet;
    pair<pair<int,int>,pair<int,int>> dirP;
    pair<int,int> nP,prevP;
    nP.first=0, nP.second=0;
    yxSet.insert(nP);
    for (int i=0; i<arrows.size(); i++)
    {
        for (int j=0; j<2; j++)
        {            
            prevP=nP;
            ny+=dy[arrows[i]],nx+=dx[arrows[i]];
            nP.first=ny, nP.second=nx;
            dirP=make_pair(prevP,nP);
            if (yxSet.find(nP)==yxSet.end())
            {
                yxSet.insert(nP);
            }
            else
            {
                if(dirSet.find(dirP)==dirSet.end())
                {
                    answer+=1;
                }
            }
            dirSet.insert(dirP);
            dirP=make_pair(nP,prevP);
            dirSet.insert(dirP);
        }
    }
    return answer;
}

 

---

 

이 문제는 그림을 그려 방이 어떻게 만들어지는지 생각해보면 쉽게 풀 수 있는 문제다.

그래서 처음에 너무 쉽게 풀리는 것 같아 이게 맞나? 생각이 들었었다.

 

프로그래머스