[C++/PGS] Lv.5 : 방의 개수 (그래프)

https://school.programmers.co.kr/learn/courses/30/lessons/49190?language=cpp

 

문제 설명

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

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

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

제한사항

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

 

---

 

구현 자체는 어렵지 않다.

 

다만 한번 방문했던 노드를 다른 경로에서 다시 방문하게 되면 방이 만들어지는데,

map을 사용해서 node, edge의 방문을 체크하는 걸 떠올리는게 힘들었음

 

대각선으로 가로지르는 X 모양의 방이 생길 경우를 위해

arrow 값을 두번 이동시켜주는 아이디어가 중요한 것 같다.

이건 나도 구글링해서 알아낸거....ㅎ

 

 

 

 나의 풀이

#include <string>
#include <vector>
#include <map>
using namespace std;

int dx[8] = { -1, -1, 0, 1, 1, 1, 0, -1 };
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };

int solution(vector<int> arrows) {
    map<pair<int, int>, bool> nodeVisited;
    map<pair<pair<int, int>, pair<int, int>>, bool> edgeVisited;
    int answer = 0;
    int x = 0;
    int y = 0;
    nodeVisited[{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(nodeVisited[{nx,ny}]==true && edgeVisited[{{x,y},{nx,ny}}]==false){
                answer++;
            }
            else {
                nodeVisited[{nx,ny}]=true;
            }
            edgeVisited[{{x,y},{nx,ny}}]=true;
            edgeVisited[{{nx,ny},{x,y}}]=true;
            x=nx;
            y=ny;
        }
    }
    return answer;
}