프로그래머스 그래프 방의개수 C++ 풀이

문제 설명

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

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

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

제한사항

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

입출력 예

arrowsreturn

[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

 

 

 

문제 풀이

처음엔 방문한 점의 좌표를 저장하고 그 좌표를 재방문 했을 때 count++ 하려고 했는데 생각해보니 그렇게 간단하지 않았다.

그래프 너무 어렵고.. 구조 어떻게 짜야할지 감이 안와서 구글링함 당연함

구글링해서 node_visited랑 edge_visited 구조만 보고 다시 풀어보기로 함.

일단 0-7 방향대로 움직일 때 dx, dy는 다음과 같다.

	0	1	2	3	4	5	6	7
x	-1	-1	0	1	1	1	0	-1
y	0	1	1	1	0	-1	-1	-1

arrows의 모든 원소를 돌면서 1. 현재 방문한 노드가 이전에 방문한 적이 있고 && 2. 이전 노드와 이루는 간선을 방문한 적이 없으면 방이 하나 만들어진거다.
이전 좌표와 현재 좌표의 값을 방문한 node_visited와 edge_visited 에 저장한다.

코드는 다음과 같다. 

int solution(vector<int> arrows) {
    int answer = 0;
    map<pair<int,int>, bool> node_visited;
    map<pair<pair<int,int>, pair<int, int>>, bool> edge_visited;
    
    int x=0,y=0;
    node_visited[{x, y}] = true;
    
    for (auto arrow : arrows) {
        int posX = x + dx[arrow];
        int posY = y + dy[arrow];

        if (node_visited[{posX, posY}] && !edge_visited[{{x,y}, {posX, posY}}])
            answer++;

        node_visited[{posX, posY}] = true;
        edge_visited[{{x,y}, {posX, posY}}] = true;
        edge_visited[{{posX, posY}, {x, y}}] = true;
        x = posX;
        y = posY;     
    }
    return answer;
}

틀렸음 당연함

질문 13개 정독했는데 3-9 틀렸다는 질문은 없었다... 결국 다시 구글링...^^
문제는 교차하는 케이스에서 중간의 간선이 체크가 안된거였는데, 모든 arrow에 대해 두번 씩 체크하면 문제가 해결된다.

 

 

정답 코드 및 결과

int solution(vector<int> arrows) {
    int answer = 0;
    map<pair<int,int>, bool> node_visited;
    map<pair<pair<int,int>, pair<int, int>>, bool> edge_visited;
    
    int x=0,y=0;
    node_visited[{x, y}] = true;
    
    for (auto arrow : arrows) {
        for (int i=0; i< 2; i++) {
            int posX = x + dx[arrow];
            int posY = y + dy[arrow];
            
            if (node_visited[{posX, posY}] && !edge_visited[{{x,y}, {posX, posY}}])
                answer++;
            
            node_visited[{posX, posY}] = true;
            edge_visited[{{x,y}, {posX, posY}}] = true;
            edge_visited[{{posX, posY}, {x, y}}] = true;
            x = posX;
            y = posY;            
        }
    }
    return answer;
}