c언어 16724번 피리부는 사나이 (백준)

#include <stdio.h>

int find(int p[], int x) { //노드의 부분집합의 대표 노드를 찾기
	if(x == p[x]) return x;
	return p[x] = find(p, p[x]);
}

void merge(int p[], int x, int y) { //두개의 노드가 속한 집합들을 합치기
	x = find(p, x);
	y = find(p, y);
	if(x!=y) p[x] = y;
	return;
}

int main(void)
{
	int n, m;
	scanf("%d %d",&n, &m);
	
	int p[n*m]; //노드가 속한 부분집합의 대표 노드를 담는 곳
	int ans[n*m]; //부분집합의 대표노드일 경우 1로 아니면 0
	char input[n][m+1]; //문자열 입력받는 배열
	
	for(int i=0; i<n; i++) {
		scanf("%s", input[i]);
		for(int j=0; j<m; j++) {
		p[i*m+j] = i*m+j;
		ans[i*m+j] = 0;
		}
	}
	
	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			switch(input[i][j]) { //문자로 입력받은 대로, 두개의 집합 합치기
				case 'D':
					merge(p, i*m+j, (i+1)*m+j); 
					break;
				case 'U':
					merge(p, i*m+j, (i-1)*m+j);
					break;
				case 'L':
					merge(p, i*m+j, i*m+j-1); 
					break;
				case 'R':
					merge(p, i*m+j, i*m+j+1); 
					break;
				default: printf("error"); break;	
			}
		}
	}
	
	int sum = 0;
	for(int i=0; i<n*m; i++) ans[find(p, i)] = 1; //집합들의 대표 노드 찾기
	for(int i=0; i<n*m; i++) if(ans[i]) sum++; //개수 세기
	printf("%d", sum); //출력
}

 

풀이 : union(합집합) + find(찾기)

 

0. 모든 칸을 각각의 집합으로 봅니다.

1. U D L R 을 통하여, 다른 칸으로 이동 할 때, 이 두개의 칸이 합쳐진 것으로 봅니다 (즉 집합들이 하나의 집합으로 합쳐집니다)

2. 입력받은 명렁어 대로, 집합들을 합치게 되면, 여러 부분집합들이 남게 됩니다.

3. 부분집합에서는, 쉼터가 없다면 무한히 돌게 됩니다.

4. 쉼터는 1개만 있어도 유한히 돌게 됩니다.

5. 즉 부분집합마다 쉼터가 1개가 필요하므로, 부분집합의 개수를 구하고 출력하면 됩니다.

 

 

ex)

DLLL
DRLU
RRRU

이렇게 두개의 무한 루프 (부분집합)이 생기게 되므로 쉼터는 각각 1개씩 필요하니, 총합은 2개입니다.

 

 

https://www.acmicpc.net/problem/16724

16724번: 피리 부는 사나이