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

문제 주소 : programmers.co.kr/learn/courses/30/lessons/49190

코딩테스트 연습 - 방의 개수

문제 확인

 

문제를 단순화 하기 위해 방이 만들어 지는 경우의 수를 생각 해 봅시다.

 

1. 방문한 점을 다시 방문한다.

방문한 점을 기록해 재방문 하면 방의 개수를 늘립니다.

 

2. 방문한 선을 다시 방문한다.

방의 개수를 샐 때 작은 삼각형 형태로 잘린 방도 방으로 취급합니다. 대각선으로 이동할 때 방문한 선을 다시 방문하는 경우이므로 대칭인 대각선을 방문한 적이 있다면 방 개수를 하나 더 늘려야 합니다.

방 2개

 

풀이

 

주어진 arrow의 크기는 100000 이하이므로 배열을 선언해서 방문지점을 확인하고 싶다면 100000x100000 크기의 배열을 필요로 하기 때문에 배열 대신 Map 컨테이너를 활용하여 방문한 지점을 트리 형식으로 저장하여 탐색, 삽입을 손쉽게 할 수 있도록 합니다.

arrows 벡터의 값을 읽어드리며 점을 이동시키고 방문한 점 혹은 간선을 만나게 되면 방의 개수를 하나씩 늘립니다. 한번에 점과 간선을 동시에 만나는 경우도 있으며 이는 2개를 늘려주어야 합니다.

 

코드

#include <iostream>
#include <map>
#include <string>
#include <vector>
 
 
using namespace std;
 
int dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 },
dy[] = { 1, 1, 0, -1, -1, -1, 0 ,1 };
 
int solution(vector<int> arrows) {
 
    int answer = 0;
    int cx = 0, cy = 0;
    map<pair<int, int>, bool> vtx;
    map<pair< pair<int, int>, pair<int, int>>, bool> edge;//맵 컨테이너로 방문한 점, 간선 탐색 시간 단축
    vtx[{0, 0}] = 1;
    for (auto cur : arrows) {
        int nx = cx + dx[cur], ny = cy + dy[cur];
 
        if (edge.find({ {cx, cy},{nx, ny} }) == edge.end() && edge.find({ {nx, ny},{cx, cy} }) == edge.end()) { //방문하지 않은 간선
            edge[{ {cx, cy}, { nx, ny }}] = 1;
            if (vtx.find({ nx, ny }) == vtx.end()) { //방문하지 않은 점
                vtx[{nx, ny}] = 1;
            }
            else {//방문한 점을 만나면 카운트
                answer++;
            }
 
            if (cur % 2 == 1) { //대각선 이동시 다른 대각 방향으로 방문한 간선이 있다면 카운트 추가
                if (edge.find({ {cx, ny},{nx, cy} }) != edge.end() || edge.find({ {nx, cy},{cx, ny} }) != edge.end()) {
                    answer++;
                }
            }
        }
        cx = nx; cy = ny;
 
    }
 
    return answer;
}
int main() {
    vector<int> board = { 4, 2, 0, 5, 0 };
 
 
    cout << solution(board);
}
 
/*
풀이:
map 컨테이너 활용해서 접근한 점, 간선 저장 및 탐색시간 단축
간선은 이어져 있으므로 방문한 점을 방문하게 되면 방 추가, 대각선 그리기 시 반대 대각선이 있다면 방 하나 추가
*/