[백준]피리 부는 사나이(16724)

문제 링크 : [백준]피리 부는 사나이(16724)

문제 설명

N * M 행렬이 주어지고, 각 칸에는 위, 아래, 왼쪽, 오른쪽으로 이동 할 수 있는 방향이 주어집니다.
안전지대를 지정하려는데, 어떤 칸에서 시작하더라도 안전지대에 갈 수 있어야 합니다.
안전지대를 최소 몇개를 지정해야 하는지 구하세요.

입력

N(행렬의 세로 길이, 1 <= N <= 1,000)
M(행렬의 가로 길이, 1 <= M <= 1,000)
D_ij(해당 칸에서 이동할 수 있는 방향)

3 4
DLLL
DRLU
RRRU

출력

2

카테고리

#DisjointSet

시간 복잡도 상한

O(NM)

해결 방법

1. 각 칸에서 이동가능한 칸들을 연결해보면, 그룹이 생기게 됩니다.
2. 그리고 그 그룹은 항상 한칸의 안전지대만 가져도 됨을 알 수 있습니다.
   2-1. 각 그룹별로 한 칸으로 이동지점이 수렴합니다.
3. 현재 칸과 이동 가능한 칸들을 계속 합쳐가면서 그룹을 관리하면 됩니다.
4. 그룹 관리는 DisjointSet을 사용하여 관리합니다.
5. 2차원 배열이라 두 변수를 하나의 index로 변경하는 함수만 만들면 기존의 DisjointSet과 동일합니다.

시간복잡도

O(NM)

코드

#include<iostream>
#include<string.h>
using namespace std;
int n,m,i,j,d[1000*1000],a;
char c[1001];
int f(int a){
    if(d[a]<0)return a;
    return d[a]=f(d[a]);
}
void u(int a,int b){
    int x=f(a),y=f(b);
    if(x!=y)d[x]=y;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    memset(d,-1,sizeof(d));
    for(i=0;i<n;i++){
        cin>>c;
        for(j=0;j<m;j++){
            if(c[j]=='D')u(i*m+j,(i+1)*m+j);
            if(c[j]=='U')u(i*m+j,(i-1)*m+j);
            if(c[j]=='L')u(i*m+j,i*m+j-1);
            if(c[j]=='R')u(i*m+j,i*m+j+1);
        }
    }
    for(i=0;i<n;i++)for(j=0;j<m;j++)if(d[i*m+j]<0)a++;
    cout<<a;
}