백준 16724 - 피리 부는 사나이

문제

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

풀이

주어진 맵에서는 회원이 특정 좌표에 위치했을 때 갈 수 있는 방향이 정해져 있다. 따라서 좌표의 방향 값에 따라 모일 수 있는 지점이 정해져 있다. 우선 이런 방향에 따른 탐색은 DFS를 통해 가능할 것이라고 생각하였다.

부가적으로, 이런 방향에 따라 모일 수 있는 지점들의 최소 개수를 구해야 한다. 이는 좌표들을 하나의 노드로 보고 유니온 파인드 연산을 통해 서로 이동이 가능한 분리집합을 합쳐주는 식의 접근으로 구현할 수 있다고 보았다.

이런 두 판단하에 다음 과정의 로직을 구성할 수 있다.

1. 특정 좌표에서 DFS 탐색을 진행한다. 탐색은 주어진 좌표의 방향 값에 따라 방향이 결정된다.
2. 다음 방향으로의 탐색은 현재 노드와 다음 노드가 같은 집합에 속하지 않을 경우 진행된다. 이 때 유니온 연산을 통해 두 노드가 같은 집합내에 속하도록 해준다.
3. 루트의 개수를 카운팅해준다. 이 값이 곧 최소 안전 지역의 개수이다.

한편, 유니온 파인드 로직을 편리하게 구성하기 위해 좌표마다 임의의 노드 번호를 부여해주었다. 좌표를 나타내는 임의의 클래스 Point 를 산정하고 노드 번호를 키로 하여 좌표를 Map<Integer, Point> 에 저장해주었다.

유니온 파인드의 경우 최적화된 형태로 사용하였는데 이에 대한 자세한 내용은 이 링크를 참고하자.

로직의 시간복잡도는 DFS가 최악의 경우 $O(NM)$으로 수렴하는데 이는 $N=1,000\;,M=1,000$인 최악의 경우에도 제한 조건 1초를 무난히 통과할 수 있다.

코드

import static java.lang.Integer.*;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Main {
	static Map<Integer, Point> nodePointMap = new HashMap<>();

	static int N, M;
	static char[][] direction;
	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());
		N = parseInt(st.nextToken());
		M = parseInt(st.nextToken());

		direction = new char[N][M];
		parent = new int[N * M + 1];

		int nodeNumber = 1;
		for (int r = 0; r < N; r++) {
			String line = br.readLine();
			for (int c = 0; c < M; c++) {
				direction[r][c] = line.charAt(c);
				nodePointMap.put(nodeNumber++, new Point(r, c));
			}
		}

		Arrays.fill(parent, -1);

		for (Integer node : nodePointMap.keySet()) {
			dfs(node);
		}

		int count = 0;
		for (int node = 1; node < parent.length; node++) {
			if (parent[node] < 0) {
				count++;
			}
		}

		System.out.println(count);
		br.close();
	}

	static int find(int u) {
		if (parent[u] < 0)
			return u;

		return parent[u] = find(parent[u]);
	}

	static boolean isUnion(int u, int v) {
		int r1 = find(u);
		int r2 = find(v);
		return r1 == r2;
	}

	static void union(int u, int v) {
		int r1 = find(u);
		int r2 = find(v);

		if (r1 == r2)
			return;

		if (parent[r1] < parent[r2]) {
			parent[r1] += parent[r2];
			parent[r2] = r1;
		} else {
			parent[r2] += parent[r1];
			parent[r1] = r2;
		}
	}

	static void dfs(int cur) {
		Point p = nodePointMap.get(cur);
		int next = -1;

		switch (direction[p.r][p.c]) {
			case 'L':
				next = cur - 1;
				break;
			case 'R':
				next = cur + 1;
				break;
			case 'D':
				next = cur + M;
				break;
			case 'U':
				next = cur - M;
		}

		if (!isUnion(cur, next)) {
			union(cur, next);
			dfs(next);
		}
	}

	static class Point {
		int r, c;

		public Point(int r, int c) {
			this.r = r;
			this.c = c;
		}
	}
}

결과