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

[문제링크]

16724번: 피리 부는 사나이

 

0. A칸에서 이동해 B칸으로 갈 경우, A와 B는 같은 집합에 속한다

  - 이러한 이동-집합에 대해, 각 집합당 1개의 SAFE-ZONE이 필요하게 된다

  - disjoint-set으로 집합 관리

 

1. n*m개의 각 칸을 set으로 만들고, set의 갯수 또한 n*m으로 초기화한다

 

2. 모든 칸을 순회하며 각 칸의 이동에 따라 도착지점의 set과 결합한다

 

3. 최종적으로 남아있는 set의 갯수가 필요한 SAFE-ZONE의 수가 된다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = pint(st.nextToken());
		m = pint(st.nextToken());
        
		init();
		
		for (int i = 0; i < n; i++) {
			String s =br.readLine();
			for (int j = 0; j < m; j++) {
				switch(s.charAt(j)) {
				case 'U':
					union(i*m+j, (i-1)*m+j);
					break;
				case 'D':
					union(i*m+j, (i+1)*m+j);
					break;
				case 'L':
					union(i*m+j, i*m+j-1);
					break;
				case 'R':
					union(i*m+j, i*m+j+1);
					break;
				default:
					break;
				}
			}
		}
		
		System.out.println(cntSet);
		
	}
	static int n,m;
	static int[][]parent;
	static int cntSet;
	
	static void init() {
		parent = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				parent[i][j]=m*i+j;
			}
		}
		cntSet=n*m;
	}
	
	static int find(int x) {
		if(parent[x/m][x%m]!=x)return parent[x/m][x%m]=find(parent[x/m][x%m]);
		return x;
	}
	
	static void union(int x, int y) {
		int rx = find(x), ry=find(y);
		if(rx!=ry) {
			parent[rx/m][rx%m]=ry;
			cntSet--;
		}
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면