[BOJ 16724] 피리 부는 사나이 (Java)

BOJ 16724 피리 부는 사나이

난이도 : 골드 3

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

16724번: 피리 부는 사나이

 

전략

처음에는 단순히 dfs로 탐색해서 연결된 노드들 단위로 개수를 세면 안될까?라고 접근했다.

하지만 이렇게 하면 탐색 순서에 따라 문제가 생길 수 있다.

문제에서 제시된 예시만 보면 dfs로 탐색해도 괜찮을 것 같지만

이런 경우를 보자

(row, col)로 좌표를 나타내었을 때

(1, 1)을 먼저 탐색했을 경우와 (1, 2)를 먼저 탐색했을 경우 등

정답은 1이지만, 방문 순서에 따라 1, 2, 3 등 다양한 답이 나올 것이다.

 

따라서 disjoint set을 이용해서 풀었다.

이차원으로 표현되었지만 parent 배열로 접근할 때의 효율성을 위해서 일차원 배열로 변형하였다.

r * M + c의 형태로 나타낼 수 있다.

 

find 연산을 이용해 자신이 가리키고 있는 셀의 부모 셀에 연결하는 방식으로 disjoint set을 구현하였다.

이후 parent 배열을 순회하면서 HashMap에 저장하며 집합의 개수를 세었다.

 

시행착오

시행착오는 없었다.

 

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, M;
        String[] line = br.readLine().split(" ");
        N = Integer.parseInt(line[0]);
        M = Integer.parseInt(line[1]);

        int[] parent = new int[N * M];
        for (int i = 0; i < N * M; i++)
            parent[i] = i;

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                int curIdx = i * M + j;
                int parIdx = curIdx;
                switch (str.charAt(j)) {
                    case 'D':
                        parIdx += M;
                        break;
                    case 'U':
                        parIdx -= M;
                        break;
                    case 'R':
                        parIdx += 1;
                        break;
                    case 'L':
                        parIdx -= 1;
                }

                parent[curIdx] = find(parent, parIdx);
            }
        }

        for (int i = 0; i < M * N; i++)
            parent[i] = find(parent, i);

        HashMap<Integer, Boolean> parentMap = new HashMap();
        int ans = 0;
        for (int i = 0; i < M * N; i++) {
            if (!parentMap.containsKey(parent[i])) {
                parentMap.put(parent[i], true);
                ans++;
            }
        }
        System.out.println(ans);
    }

    static int find(final int[] parent, int i) {
        if (parent[i] == i)
            return i;
        return parent[i] = find(parent, parent[i]);
    }
}

 

깨달은 점

이차원으로 표현된 자료를 disjoint set으로 어떻게 풀어낼 수 있을까 고민하면서 변형할 수 있는 능력을 키울 수 있는 문제였다.