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

문제

첫 번째 접근 방법

방이란 도형이다. 도형이란 무슨 특징을 가지고 있을까.
도형을 그으려면 다시 원점으로 돌아와야 한다. 즉 사이클이라는 것이다. 사이클이란 무엇인가 이미 도착했던 점을 다시 도착하는 것이다.
사이클을 확인하면 될 것 같다.

첫 번째 실패

이미 지나간 곳인지 확인해보는 방식으로 사이클을 확인했는데 예제만 풀고 제출에서 틀렸다.

5	4
3	0,6
1	2

모래시계와 같은 모형이면 선만 겹치고 점은 안 겹치기에 틀린 답으로 나온다.

10	9	8
	7,11
6		0,12
	1,5
2	3	4

두 배를 하고 공간을 확인하는 방식은 어떨까 싶기도 했다. (그렇다면 중간 점도 해결이 된다)

배열을 이용한 공간 탐색의 경우 시간이 오래 걸릴 것 같다. (음수로 100,000, 양수로 100,000이 나올 수 있는 2차원 배열이므로 크기도 안 될 것 같았다)
지금 사용 중인 이미 지나온 곳을 바탕으로 판단하는 것도 그대로 사용하긴 힘들 것 같다. (직선일 수도 있으니)
음수는 map으로 해결이 될 것 같기도 하고 2배를 하는 건 아이템 줍기에서도 통했으니 할 생각인데 공간 확인은 너무 오래 걸릴 것 같기도 하다. 그래서 현재 사용했던 방식은 그대로 하면서 사이클을 확인하는 방식을 개선해야 할 것 같다.

두 번째 접근 방법

일단 두 배로 하고 (아이템 줍기와 유사하다고 생각했다) 음수는 map으로 해결하더라도 선으로 이루어진 (2개의 정점을 왔다 갔다하면 도형이 아닌데도 도형으로 판단한다) 경우가 문제라고 생각했다. 방법을 찾다가 한번 다른 사람의 풀이를 보니 선을 저장해두고 확인하는 방식을 사용하던 것이다.

코드

#include <string>
#include <vector>
#include <map>
using namespace std;
int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {1, 1, 0, -1, -1, -1, 0, 1};
map<pair<int, int>, bool> visted;
map<pair<pair<int, int>, pair<int, int>>, bool> edge;
int solution(vector<int> arrows)
{
    int answer = 0;
    pair<int, int> cur = {0, 0};
    visted[cur] = true;
    for (int arrow : arrows)
    {
        for (int i = 0; i < 2; ++i)
        {
            pair<int, int> next = {cur.first + dy[arrow], cur.second + dx[arrow]};
            if (!edge[{cur, next}] && !edge[{next, cur}])
            {
                if (visted[next])
                    ++answer;
            }
            visted[next] = true;
            edge[{cur, next}] = true;
            cur = next;
        }
    }
    return answer;
}

풀이

도형이 사이클의 형태라는 것, 음수이기에 map을 쓰는 것이 좋다는 점, 2배를 해서 풀어야 한다는 점, 이미 지나온 선인 경우에는 도형에 포함되면 안 된다는 점을 알면 풀 수 있는 문제이다.
코드는 생각보다 짧게 나와서 놀랐다. 정점을 확인하는 것에 익숙해져서 간선을 확인하는 법을 생각해내지 못한 것 같다. 정답에 거의 근접했는데 좀만 더 생각해봤다면 생각해내지 않았을까 싶기도 해서 아쉽다.