(c++)프로그래머스 그래프 방의개수

문제 설명

원점(0,0)에서 시작해서 아래처럼 숫자가 적힌 방향으로 이동하며 선을 긋습니다.

ex) 1일때는 오른쪽 위로 이동

그림을 그릴 때, 사방이 막히면 방하나로 샙니다.
이동하는 방향이 담긴 배열 arrows가 매개변수로 주어질 때, 방의 갯수를 return 하도록 solution 함수를 작성하세요.

 

제한사항

• 배열 arrows의 크기는 1 이상 100,000 이하 입니다.
• arrows의 원소는 0 이상 7 이하 입니다.
• 방은 다른 방으로 둘러 싸여질 수 있습니다.
•  

입출력 예

arrows	return
[6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0]	3

 

입출력 예 설명

• (0,0) 부터 시작해서 6(왼쪽) 으로 3번 이동합니다. 그 이후 주어진 arrows 를 따라 그립니다.
• 삼각형 (1), 큰 사각형(1), 평행사변형(1) = 3

 

---

 

나의 풀이

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <iostream>

using namespace std;

int solution(vector<int> arrows) {
    vector<int> x = { 0,1,1,1,0,-1,-1,-1 };
    vector<int> y = { 1,1,0,-1,-1,-1,0,1 };
    map<pair<int, int>, bool> visited_node; //위치를 저장
    map<pair<pair<int, int>, pair<int, int>>, bool> visited_edge; //방향(노드)을 저장
    int answer = 0;
    pair<int, int> now = { 0,0 }; //현재위치
    visited_node.insert({ now, true });
    for (int i = 0; i < arrows.size(); i++) {
        for (int k = 0; k < 2; k++) {
            pair<int, int> after = { now.first + x[arrows[i]],now.second + y[arrows[i]] }; //다음 위치
            if (visited_node.find(after) != visited_node.end()) { 
                if (visited_edge.find(make_pair(now, after)) == visited_edge.end()) {
                    answer++;
                }
            }
            visited_node.insert({ after, true });
            visited_edge.insert({ make_pair(now,after),true });
            visited_edge.insert({ make_pair(after,now),true });
            now = after;
        }
    }
    return answer;
}

 

방법을 생각해내기까지 조금 어려웠다. 블로그를 참고하여 방법을 이해해냈다.

양방향 노드를 저장해야하는데 이를 생각하지 못했다.

방향을 저장하는 것을 노드를 저장하는 것으로 사용하는 것을 생각하지 못했다.