Programers : 방의 개수 - C++

김정욱·2021년 3월 19일

DFS Graph PROGRAMERS level3

Algorithm - 문제

목록 보기

168/249

방의 개수

코드

[ DFS 풀이 ]

#include <string>
#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
// 2차원 좌표로 이루어진 그래프에서 순환 검사 + 예외처리
map<pair<int,int>, vector<pair<int,int>>> m;
map<pair<int,int>, bool> vis;
map<pair<pair<int,int>, pair<int,int>>, bool> make;
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int ans=0;
void DFS(int Y, int X){
    vis[{Y,X}] = true;
    for(int i=0;i<m[{Y,X}].size();i++){
        int ny = m[{Y,X}][i].first;
        int nx = m[{Y,X}][i].second;
        bool check = false;
        if(make[{{Y,X}, {ny,nx}}] or make[{{ny,nx}, {Y,X}}]) check = true;
        /* 해당 정점에 대해 방문하였으면서 && 처음 만들어지는 간선이면! */
        if(vis[{ny,nx}] and !check) ans++;
        else if(vis[{ny,nx}]) continue;
        /* 간선은 하나지만, 방향은 2개가 될 수 있기에 2방향 모두 넣어줘야함 */
        make[{{Y,X}, {ny,nx}}] = true;
        make[{{ny,nx}, {Y,X}}] = true;
        DFS(ny, nx);
    }
}
int solution(vector<int> arrows) {
    int curX = 0;
    int curY = 0;
    for(int i=0;i<arrows.size();i++)
    {
        /* 교차 예외 처리를 위해 2번식 이동 */
        for(int j=0;j<2;j++)
        {
            int nx = curX + dx[arrows[i]];
            int ny = curY + dy[arrows[i]];
            bool flag = false;
            m[{curY, curX}].push_back({ny, nx});
            curY = ny;
            curX = nx;
        }
    }
    DFS(0,0);
    return ans;
}