[BOJ] 16724 : 피리 부는 사나이 (C++)

📖 백준 16724번 : https://www.acmicpc.net/problem/16724

조건

시간 제한	메모리 제한
1 초	256 MB

문제

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

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

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

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

입력

첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다.

두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주어진다.

지도 밖으로 나가는 방향의 입력은 주어지지 않는다.

출력

첫 번째 줄에 ‘SAFE ZONE’의 최소 개수를 출력한다.

---

풀이

 영과일 회원들이 움직일 수 있는 경로의 집합을 생각해보자. 각 집합의 개수는 SAFE ZONE의 최소 개수와 동일하다. 회원들이 움직이는 경로는 정해져있고 각 경로의 루트 노드에 SAFE ZONE을 두었을 때, 경로에 존재하는 모든 회원은 SAFE ZONE에 들어갈 수 있다. 따라서 회원들이 움직이는 경로, 즉 영역이 얼마나 존재하는지 파악하면 된다.

 보통 Union-Find로 푸는 것 같은데, dfs로도 각 경로의 개수를 구할 수 있을 것 같았다. 현재 탐색인지 이전 탐색인지를 파악하는 상태 정보를 통해서 경로를 구분하고, 현재 탐색 중에 지나왔던 길에 다시 도달하면 SAFE ZONE의 개수가 늘어난 것이다. 만약 이전 탐색 중에 지나왔던 길에 도달한다면 지금 탐색하고 있던 경로는 새로운 경로가 아니라 이전 경로의 연장선이기 때문에 SAFE ZONE의 개수가 늘지 않는다.

 현재 탐색인지 이전 탐색인지 구분하는 상태 정보를 3차원 visited 배열로 저장했다. dfs를 끝낸 후에 탐색했던 경로는 과거의 경로가 되었기 때문에 갱신해준다.

코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool visited[1000][1000][2];//0 현재 탐색 중인지, 1 과거의 탐색했던 값인지 파악
char space[1000][1000];
vector<pair<int, int>> update;
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
int ans = 0;

void dfs(int y,int x) {
    update.push_back({ y,x });//현재 탐색 중인 값을 저장
    visited[y][x][0] = true;

    int next;
    switch (space[y][x]) {
    case 'U': next = 0; break;
    case 'D': next = 1; break;
    case 'L': next = 2; break;
    case 'R': next = 3; break;
    }
    y += dy[next];
    x += dx[next];

    if (visited[y][x][0]) {//현재 탐색 중인 경로에 이어짐, 새로운 경로
        ans++;
        return;
    }
    else if (visited[y][x][1]) return;//이전 탐색 경로에 이어짐, 경로 동일
    else dfs(y, x);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) 
            cin >> space[i][j];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (!visited[i][j][1]) {
                dfs(i, j);
                //탐색했던 경로를 이전 탐색으로 갱신
                for (int i = 0; i < update.size(); i++) {
                    int y = update[i].first;
                    int x = update[i].second;

                    visited[y][x][0] = false;
                    visited[y][x][1] = true;
                }
                update = vector<pair<int, int>>();//초기화
            }
        }
    }
    cout << ans;

    return 0;
}