[BOJ / C++] 16724번 : 피리 부는 사나이

문제

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

성우가 피리를 불 때면 영과일 회원들은 자기도 모르게 성우가 정해놓은 방향대로 움직이기 시작한다. 성우가 정해놓은 방향은 총 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’의 최소 개수를 출력한다.

Solved.ac 레벨

골드 III

풀이

3 4
DLLL
DRLU
RRRU

예제 입력과 예제 입력을 그림으로 나타낸 것을 보면 위와 같다.

예제 입력을 그림으로 나타낸 것을 확인해 보면 화살표를 따라 진행했을 때 사이클이 발생하는 곳에 안전 지대를 만들 수 있는 것을 확인할 수 있다. 따라서 만들 수 있는 안전 지대의 개수는 그래프 내의 사이클 개수와 같다.

 

그래프에서의 사이클 판별은 최소 스패닝 트리를 만들 때 크루스칼 알고리즘을 구현하며 합집합 알고리즘을 활용할 때도 찾을 수 있지만 DFS로도 찾을 수 있기 때문에 DFS로 사이클을 판별하고 사이클의 개수를 세주었다.

 

그래프에 입력으로 주어지는 U, D, L, R은 다음 탐색의 이동방향이므로 다른 그래프 탐색 문제에서 인접한 상하좌우로 탐색할 때 dx, dy 배열을 만들어서 다음 진행방향을 결정했던 것처럼 D, U, L, R 순서로 {1, 0}, {-1, 0}, {0, -1}, {0, 1}로 사용할 수 있게 입력받는 즉시 해당 방향 배열의 인덱스로 치환해서 MAP에 저장해주었다.

 

사이클 판단은 y = 1, x = 1로 가정했을 때 이를 인자로 호출한 DFS 함수에서 다음 탐색 좌표가 이미 DFS를 수행하고 방문한 위치라면 집계해주는 방법으로 해주었다.

Code

#include <bits/stdc++.h>
#define MAX 1001

using namespace std;

int n, m, ans;
int MAP[MAX][MAX];
int dy[4] = {1, -1, 0, 0}; //D, U, L, R
int dx[4] = {0, 0, -1, 1}; // D, U, L, R
int visited[MAX][MAX];

void DFS(int y, int x) {
    visited[y][x] = 1;

    int ny = y + dy[MAP[y][x]];
    int nx = x + dx[MAP[y][x]];

    if(visited[ny][nx] == 1) {
        //이미 방문했다면 사이클 발생
        ans++;
    }

    if(visited[ny][nx] == 0) {
        DFS(ny, nx);
    }

    visited[y][x] = 2;
}

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

    cin >> n >> m; //y, x

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;

        for(int j = 0; j < m; j++) {
            if(str[j] == 'U') MAP[i][j] = 1;
            else if(str[j] == 'L') MAP[i][j] = 2;
            else if(str[j] == 'R') MAP[i][j] = 3;
        }
    }

    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(visited[i][j] == 0) DFS(i, j);
        }
    }

    cout << ans << "\n";

    return 0;
}

16724번: 피리 부는 사나이