[고득점Kit][그래프] 방의 개수 ⭐⭐⭐⭐⭐

[그래프] 방의 개수

난이도 ⭐⭐⭐⭐⭐

문제

풀이

코드, 풀이 참고 : 얍문님 블로그 https://yabmoons.tistory.com/606

Lv.5 난이도에 지레 겁먹고 구글링부터 했었던 문제였다. 나름 생각보다 복잡한 답은 아니길래 좀 더 깊게 고민 해 볼걸 그랬나 싶다. 이 분이 너무 설명을 잘 해주셔서 그렇게 느낀걸까..😂 이 분의 포스트를 통해 명쾌하게 이해가 되었다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> arrows) {
    int answer = 0;
    
    vector<int> dx = { 0, 1, 1, 1, 0, -1, -1, -1 };
    vector<int> dy = { 1, 1, 0, -1, -1, -1, 0, 1 };
    
    map<pair<int, int>, bool> visitedNode;
    map<pair<pair<int, int>, pair<int, int>>, bool> visitedEdge;
    
    int curX = 0;
    int curY = 0;
    visitedNode[make_pair(0, 0)] = true;
    
    for(int i = 0; i < arrows.size(); i++)
    {
        for(int j = 0; j < 2; j++)  
        {
            int nextX = curX + dx[arrows[i]];
            int nextY = curY + dy[arrows[i]];
            
            if (visitedNode[make_pair(nextX, nextY)] == true && visitedEdge[make_pair(make_pair(curX, curY), make_pair(nextX, nextY))] == false)
                answer++;
            
            visitedNode[make_pair(nextX, nextY)] = true;
            visitedEdge[make_pair(make_pair(curX, curY), make_pair(nextX, nextY))] = true;
            visitedEdge[make_pair(make_pair(nextX, nextY), make_pair(curX, curY))] = true;

            curX = nextX;
            curY = nextY;
        }
    }
    return answer;
}

• 예를 들어 5 방향으로 가야 한다면 수평 방향으로 dx[5]만큼, 이와 동시에 수직 방향으로는 dy[5]만큼 가도록 미리 dx, dy 배열을 만들어 두었다. 오른쪽, 위쪽은 양수, 왼쪽, 아래쪽은 음수로 설정했다.1만큼 움직인다고 설정하였다.

---

방이 만들어지는 조건 (아래 조건들이 모두 만족해야 한다.)

1. 기존에 방문했던 정점을 재방문
   • 1만 만족하면 하나의 동일한 선분 내에서 왔다 갔다 하는 것도 방으로 칠 수 있게 된다. 선분은 방이 될 수 없다. 1만 만족하면 안된다.

       visitedNode[make_pair(nextX, nextY)] == true
     

2. 해당 간선은 기존에 방문한적이 없던 간선

     visitedEdge[make_pair(make_pair(curX, curY), make_pair(nextX, nextY))] == false
   

---

• visitedNode
  • 정점 방문 체크. 조건 1️⃣ 에 의하여 필요하다.
  • Key 는 (x, y) 정점의 위치가 되며, Value 는 방문 여부인 Bool 값이다.
  • 출발 정점인 (0, 0)은 미리 방문 체크 해둔다.
• visitedEdge
  • 간선 방문 체크. 조건 2️⃣ 에 의하여 필요하다.
  • Key 는 ((x1, y2), (x2, y2)) 이렇게 (x1, y2) 정점에서 (x2, y2) 로 향하는 간선이 되며, Value 는 방문 여부인 Bool 값이다.
• curX ,curY 는 매번 업데이트 될 현재 방문 중인 정점의 위치를 뜻한다. 각각 0이 초기값이다. (출발지 0, 0)

---

주의해야할 점

두 간선의 교차점이 정점이 아닐 때도 방이 만들어질 수 있음을 인지해야 한다. dx, dy 한 칸씩 움직이게 설정했었기 때문에 이로 따지면 (0.5, 0.5) 지점 정도에서도 간선간의 교차가 이루어질 수 있는 것이다. 이런 경우에도 방이 만들어질 수 있다. 정점 위치는 정수만 취급할 것이기 때문에(정수가 편해서) (0.5, 0.5) 이런 정점에서 교차되는 경우도 발견할 수 있기 위하여 2 배로 늘려 (0.5, 0.5)를 (1, 1)로 만든다 생각하고 dx, dy를 총 2 번 이동하기로 하자. 즉 검사도 2번 이루어짐. 교차가 정점 위에서만 이루어지도록 ! (그래야 1️⃣조건도 따질 수 있다.)

for(int j = 0; j < 2; j++) 

---

• 다음 정점으로 이동 nextX, nextY

  int nextX = curX + dx[arrows[i]];
  int nextY = curY + dy[arrows[i]];
  

• 다음 정점으로 이동할 때 방이 생성되는 조건에 만족하는지 검사. 맞다면 answer++

  if (visitedNode[make_pair(nextX, nextY)] == true && visitedEdge[make_pair(make_pair(curX, curY), make_pair(nextX, nextY))] == false)
        answer++;
  

• 다음 정점 방문 체크, 간선 방문 체크

    visitedNode[make_pair(nextX, nextY)] = true;
  
    visitedEdge[make_pair(make_pair(curX, curY), make_pair(nextX, nextY))] = true;
    visitedEdge[make_pair(make_pair(nextX, nextY), make_pair(curX, curY))] = true;
  

• 다음 정점으로 본격 이동하기

  curX = nextX;
  curY = nextY;
  

---

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Programmers 카테고리 내 다른 글 보러가기