유니온 파인드를 사용하는 문제
만약 한번도 방문하지 않은 칸이라면 cnt와sum을 1씩 더해주고 위의 재귀문을 통하여 화살표 방향이 막힐때까지 재귀로 방문을 진행한다.
visit에 카운트 수를 넣어줘서 체크한다.
만약 막히는 경우가
1. 이미 방문한 칸을 만난 경우
이때 visit 배열의 수를 봐서
- 다른 수의 visit를 만났다면
SafeZone을 만든 곳과 이어졌다는 뜻이므로 SafeZone을 또 만들 필요가 없다.
따라서 재귀를 시작할때 sum에 1을 더해준 것을 빼서 돌려놓는다. - 같은 수의 visit를 만났다면
한 구역이 형성됐다는 뜻이다.
위의 경우와는 다르게 SafeZone이 필요하므로 그대로 진행한다.
2. 배열의 밖을 벗어난 경우
역시 일단은 SafeZone이 필요하다.
따라서 그대로 진행한다.(sum에 1을 다시 빼지 않는다)
위의 방법을 반복하여 sum을 구하면 답이 된다.
(재귀로 visit를 체크해주는 코드이다.)
void move(int x,int y,int cnt){
visit[x][y]=cnt;
if(arr[x][y]=='R'&&y+1!=N){
if(visit[x][y+1]!=0){
if(visit[x][y+1]!=cnt){
sum--;
}
}else{
move(x,y+1,cnt);
}
}else if(arr[x][y]=='L'&&y!=0){
if(visit[x][y-1]!=0){
if(visit[x][y-1]!=cnt){
sum--;
}
}else{
move(x,y-1,cnt);
}
}else if(arr[x][y]=='U'&&x!=0){
if(visit[x-1][y]!=0){
if(visit[x-1][y]!=cnt){
sum--;
}
}else{
move(x-1,y,cnt);
}
}else{
if(visit[x+1][y]!=0){
if(visit[x+1][y]!=cnt){
sum--;
}
}else{
move(x+1,y,cnt);
}
}
}전체코드
#include <stdio.h>
char arr[1001][1001];
int visit[1001][1001];
int cnt=0;
int M,N;
int sum=0;
void move(int x,int y,int cnt){
visit[x][y]=cnt;
if(arr[x][y]=='R'&&y+1!=N){
if(visit[x][y+1]!=0){
if(visit[x][y+1]!=cnt){
sum--;
}
}else{
move(x,y+1,cnt);
}
}else if(arr[x][y]=='L'&&y!=0){
if(visit[x][y-1]!=0){
if(visit[x][y-1]!=cnt){
sum--;
}
}else{
move(x,y-1,cnt);
}
}else if(arr[x][y]=='U'&&x!=0){
if(visit[x-1][y]!=0){
if(visit[x-1][y]!=cnt){
sum--;
}
}else{
move(x-1,y,cnt);
}
}else{
if(visit[x+1][y]!=0){
if(visit[x+1][y]!=cnt){
sum--;
}
}else{
move(x+1,y,cnt);
}
}
}
int main(){
scanf("%d %d",&M,&N);
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
scanf(" %c",&arr[i][j]);
}
}
for(int i=0;i<M;i++){
for(int j=0;j<N;j++){
if(visit[i][j]==0){
move(i,j,++cnt);
sum++;
}
}
}
printf("%d",sum);
}