[알고리즘] c++ cpp 방의 개수

포인트

1. map 을 사용하여 방문상태와 연결 상태를 확인한다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

#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 };

struct Point {
    int x, y;
};

int solution (vector<int> arrows) {
    int room=0;
    map<pair<int, int>, int> visited;
    map<pair<pair<int, int>, pair<int, int>>, int> connected;

    Point point={ 0,0 };

    visited[{point.x, point.y}]=1;
    for (int i=0; i < arrows.size (); i++) { // point.x자의 교차 형태도 세줘야해서 2배
        for (int j=0; j < 2; j++) {
            int nx=point.x + dx[arrows[i]];
            int ny=point.y + dy[arrows[i]];

            if (visited[{nx, ny}] == 1) {
                if (connected[{ {point.x, point.y}, { nx, ny }}] == 0 || connected[{ {nx, ny}, { point.x, point.y }}] == 0) {
                    room++;
                }
            }
            // vertex 체크
            visited[{nx, ny}]=1;

            // edge 체크
            connected[{ {point.x, point.y}, { nx, ny }}]=1;
            connected[{ {nx, ny}, { point.x, point.y }}]=1;

            point={ nx, ny };
        }
    }

    return room;
}