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

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

16724번: 피리 부는 사나이

 

전체 로직

1. 정해진 방향을 따라서 닿을 수 있는 곳들은 한 그룹으로 묶어준다.
2. 그룹 당 하나의 SAFE ZONE만 있으면 그룹 안의 모든 위치에서 SAFE ZONE에 도달할 수 있다.
3. 그룹의 개수를 출력한다.

→ 그룹의 개수를 찾기 위해 union find를 사용하였다. 그러나 BFS, DFS를 사용해도 될 것 같다!(다음에 풀어보겠다….)

유의해야할 점은 p의 index이다. 이차원 배열을 사용하면 처리가 복잡해질 것 같아서 1차원 배열로 선언하였고 이때 index를 조심해서 넣어주어야 한다!

예제는 N, M이 같으므로 유념하자!

전제 코드

import java.util.*;
import java.io.*;

public class Main{
	static int[] p;
	static int N;
	static int M;
	static char[][] map;
    public static void main(String args[]) throws Exception{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        p = new int[N*M];
        map = new char[N][M];
        for(int i=0; i<N; i++) {
        	String s = bf.readLine();
        	for(int j=0; j<M; j++) {
        		map[i][j] = s.charAt(j);
        		p[i*M+j] = i*M+j;
        	}
        }
        
        for(int i=0; i<N; i++) {
        	for(int j=0; j<M; j++) {
        		int ni = i; int nj = j;
        		if(map[i][j] == 'U') 	  ni--;
        		else if(map[i][j] == 'D') ni++;
        		else if(map[i][j] == 'R') nj++;
        		else 					  nj--;
        		union(i*M+j, ni*M+nj);
        	}
        }
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<N; i++)
        	for(int j=0; j<M; j++)
        		set.add(find_parent(i*M+j));
        System.out.println(set.size());
        
    }
    static void union(int a, int b) {
    	int A = find_parent(a);
    	int B = find_parent(b);
    	if(A < B) p[B] = A;
    	else p[A] = B;
    }
    static int find_parent(int a) {
    	if(p[a] == a) return a;
    	else return p[a] = find_parent(p[a]);
    }

}