백준 16724 피리 부는 사나이 (Gold 3)

전략

• 다음 문제를 푸는데 가능한 방법은 2가지가 존재한다

1. DFS를 이용해서 2차원 배열을 순회하면서 영역을 체크하는 것
2. 분리집합, 유니온-파인드를 이용해서 현재 영역과 다음 영역의 집합 형성 여부를 알아보는 것

두 문제 다 O(N^2)의 시간 복잡도를 가지고 있어서 실행시간엔 큰 차이가 있진 않다

정답코드

1. DFS 이용

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

public class PipeBlowingMan1 {

	static int R;
	static int C;
	static String[][] map;
	static boolean[][] visited;
	static int SafetyZone = 1;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new String[R][C];
		visited = new boolean[R][C];

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().split("");
		}
		
        //2차원 배열 순회하면서 방문하지 않았을 때 새로운 영역시작
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				if (!visited[i][j]) {
					followDirection(i, j, map[i][j]);

				}
			}
		}

		System.out.println(SafetyZone - 1);

	}

	public static void followDirection(int x, int y, String d) {
		
		int dir = -1;
		visited[x][y] = true;
		
        //DFS를 진행중인 영역은 "X"로 표시되고, 이미 탐색이 끝난 곳은 "O"로 표시
        //만약 탐색을 하다가 visited가 true이고 "X"이면 독립영역
        //visited가 false이고 "O"이면 다른 영역과 합쳐지는 영역이다 
		map[x][y] = "X"; 
		switch (d) {
		case "U": {
			dir = 0;
		}
			break;

		case "D": {
			dir = 1;
		}
			break;

		case "L": {
			dir = 2;
		}
			break;

		case "R": {
			dir = 3;
		}
			break;
		}

		int nx = x + dx[dir];
		int ny = y + dy[dir];

		if(visited[nx][ny] == false) {
			followDirection(nx, ny, map[nx][ny]);
		}else {
        	//자기자신과 부딪힐 때만 영역 추가 
			if(map[nx][ny] == "X")SafetyZone++;
		}
		
        //탐색이 모두 끝나면 O로 다 바꿔주기
		map[x][y] = "O"; 
		
		return;
	}
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class PipeBlowingMan2 {

	static int R;
	static int C;
	static String[][] map;
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		R = Integer.parseInt(st.nextToken());
		C = Integer.parseInt(st.nextToken());
		map = new String[R][C];
		parent = new int[R * C];

		for (int i = 0; i < R; i++) {
			map[i] = br.readLine().split("");
		}

		// 부모노드 초기화 (2차원 배열을 1차원으로)
		for (int i = 0; i < R * C; i++) {
			parent[i] = i;
		}
		
		//2차원 배열을 순회하면서 지금 노드와 다음 노드를 Union-find
		for (int i = 0; i < R; i++) {
			for (int j = 0; j < C; j++) {
				int cur = i*C+j;
				int nxt = followDirection(i, j, map[i][j]);
				if(!equals(cur, nxt))union(cur, nxt);
			}
		}
		
		
		//경로 압축 유니온 파인드를 쓰면 제대로 업데이트가 안 되는 경우가 발생 
		//다시 한 번 find를 하는 과정에서 해결이 가능하다
		for(int i = 0; i < R*C; i++) {
			parent[i] = find(i);
		}
		
		//set에 넣어서 집합의 갯수를 카운팅
		Set<Integer> s = new HashSet<>();
		for (int i = 0; i < R * C; i++) {
			s.add(parent[i]);
		}
		
		System.out.println(s.size());
		

	}

	//방향에 따른 다음 좌표 리턴 
	public static int followDirection(int x, int y, String d) {

		switch (d) {
		case "U": return (x-1)*C+y;
		case "D": return (x+1)*C+y;
		case "L": return x*C+(y-1);
		case "R": return x*C+(y+1);
		}
		
		return -1;

	}

	// a,b의 대소관계에 따라서 부모노드를 바꿔준다
	public static void union(int a, int b) {
		// 최상위 부모 찾기
		int x = find(a);
		int y = find(b);

		if (x < y) {
			parent[y] = x;
		} else {
			parent[x] = y;
		}
	}

	// a와 b의 부모가 같은지 확인
	public static boolean equals(int a, int b) {
		int x = find(a);
		int y = find(b);
		return x == y;
	}

	// a의 부모노드를 찾는 연산
	public static int find(int a) {
		if (parent[a] == a)
			return a;
		return parent[a] = find(parent[a]);
	}

}