[백준 C++] 16724번 피리 부는 사나이

16724번: 피리 부는 사나이

문제 요약

문제

피리 부는 사나이 성우는 오늘도 피리를 분다.

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 4가지로 U, D, L, R이고 각각 위, 아래, 왼쪽, 오른쪽으로 이동하게 한다.

이를 지켜보던 재훈이는 더 이상 움직이기 힘들어하는 영과일 회원들을 지키기 위해 특정 지점에 ‘SAFE ZONE’ 이라는 최첨단 방음 시설을 만들어 회원들이 성우의 피리 소리를 듣지 못하게 하려고 한다. 하지만 예산이 넉넉하지 않은 재훈이는 성우가 설정해 놓은 방향을 분석해서 최소 개수의 ‘SAFE ZONE’을 만들려 한다.

성우가 설정한 방향 지도가 주어졌을 때 재훈이를 도와서 영과일 회원들이 지도 어느 구역에 있더라도 성우가 피리를 불 때 ‘SAFE ZONE’에 들어갈 수 있게 하는 ‘SAFE ZONE’의 최소 개수를 출력하는 프로그램을 작성하시오.

사용 알고리즘

DFS, 그래프

입출력

• 입력: 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다. 지도 밖으로 나가는 방향의 입력은 주어지지 않는다.
• 출력: 첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다. ``` 예제1

입력 3 4 DLLL DRLU RRRU 출력 2

## 풀이
이 문제는 SAFE ZONE이 함정이다. SAFE ZONE의 위치는 중요하지 않고 그것은 단지 사이클이 몇개 있는지 확인하는 용도이다. 결국 이문제는 사이클이 몇개 존재하는지 구하는 문제이다. DFS를 이용하여 맵의 방향대로 이동하고 이동하다 사이클이 생성되거나 이미 사이클인 곳에 도착하면 멈춘다. 사이클을 생성했으면 SAFE ZONE을 하나 추가하고, 사이클인 곳에 도착한거면 그냥 넘어간다. 

## 어려웠던 점
딱히 없다. D의 방향을 올라가는 방향으로 했었다 정도?

## 배운 점 / 느낀 점
union코드로도 짤 수있을거 같은데 더 복잡할것 같다. 하지만 속도는 더 빠를수도 있을거 같기도 하다. 확실하진 않다.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, s;

vector<vector<char>> map;
vector<vector<bool>> a;
vector<vector<bool>> t;

void cycle(int y, int x){
    if(a[y][x]){
        return;
    }
    else if(t[y][x]){
        s++;
        a[y][x] = true;
        return;
    }
    else{
        t[y][x] = true;
    }
    if(map[y][x] == 'D'){
        cycle(y+1, x);
    }
    else if(map[y][x] == 'U'){
        cycle(y-1, x);
    }
    else if(map[y][x] == 'L'){
        cycle(y, x-1);
    }
    else if(map[y][x] == 'R'){
        cycle(y, x+1);
    }
    a[y][x] = true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;

    map = vector<vector<char>>(n, vector<char>(m));
    a = vector<vector<bool>>(n, vector<bool>(m, false));
    t = vector<vector<bool>>(n, vector<bool>(m, false));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> map[i][j];
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if(!a[i][j]){
                cycle(i, j);
            }
        }
    }
    cout << s;
    return 0;
}