문제 링크 : https://www.acmicpc.net/problem/16724
이 문제는 유니온 파인드와 dfs를 이용하여 풀 수 있습니다.
문제에서 요구하는 SAFE ZONE은 결국 사이클의 개수가 됩니다. 왜냐하면 각 위치에서 사람들이 이동하는 방향은 정해져있기 때문에 하나의 사이클 중 한 군데를 막으면 사이클 내의 모든 사람들이 접근할 수 있기 때문입니다.
이를 구현하기 위해 dfs와 유니온 파인드를 사용했습니다. 부모 배열의 경우 ixM+j의 형태로 좌측 상단부터 우측 하단 방향으로 0부터 1씩 증가하는 식으로 아이디를 부여했습니다. 이후 방문하지 않은 위치를 하나씩 dfs 탐색하여 그래프에 주어진 방향대로 이동시킵니다. 이 때 유니온 연산을 진행하여 이동 가능한 노드끼리 부모 배열을 같에 맞춰줍니다. 여기서 이미 방문한 노드에 도착했을 때 부모 배열값이 같다면 같은 사이클로 간주하여 카운트를 증가시켜줍니다.
다음은 코드입니다.
import java.util.*;
import java.io.*;
class Main{
static int N,M;
static Map<Character,Integer> dy = new HashMap<>(), dx = new HashMap<>();
static char[][] graph;
static int[][] parent;
static boolean[][] check;
static int res = 0;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new char[N][M];
for(int i=0;i<N;i++){
String str = br.readLine();
for(int j=0;j<M;j++) graph[i][j] = str.charAt(j);
}
parent = new int[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
parent[i][j] = i*M+j;
}
}
dy.put('D',1);
dy.put('U',-1);
dy.put('L',0);
dy.put('R',0);
dx.put('D',0);
dx.put('U',0);
dx.put('L',-1);
dx.put('R',1);
check = new boolean[N][M];
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(!check[i][j]) dfs(i,j);
}
}
System.out.println(res);
}
static void dfs(int y, int x){
check[y][x] = true;
int ny = y + dy.get(graph[y][x]);
int nx = x + dx.get(graph[y][x]);
if(ny<0 || ny>=N || nx<0 || nx>=M) return;
if(!check[ny][nx]){
union(y,x,ny,nx);
dfs(ny,nx);
}
else{
if(parent[y][x] == parent[ny][nx]) res++;
}
}
static void union(int sy, int sx, int ey, int ex){
int s = find(sy,sx);
int e = find(ey,ex);
if(s!=e) parent[ey][ex] = s;
}
static int find(int y, int x){
if(parent[y][x] == y*M+x) return parent[y][x];
else{
int ny = parent[y][x]/M;
int nx = parent[y][x]%M;
return parent[y][x] = find(ny,nx);
}
}
}