📙[Algo] 24.04.23 알고리즘

알고리즘 문제) BOJ 16724. 피리 부는 사나이

16724번: 피리 부는 사나이

문제 요약

• N*M 지도가 있고, 각 칸에 움직일 수 있는 방향이 적혀있음
• 움직일 수 있는 방향
  • U : 위쪽
  • D : 아래쪽
  • L : 왼쪽
  • R : 오른쪽
• 이때, 더 이상 움직일 수 없을 때 특정 지점에 SAFE ZONE을 설치하려고 함
  • SAFE ZONE은 어느 구역에 있더라도 들어갈 수 있을 것
• 이때 SAFE ZONE의 최소 개수 출력하기

시간 제한

• 1초

입력

• 지도 행 개수 N, 열 개수 M
  • 1 ≤ N ≤ 1000
  • 1 ≤ M ≤ 1000
• N개의 줄에 길이가 M인 문자열이 주어짐(지도 정보)
  • 지도 밖으로 나가는 방향은 없다.

출력

• SAFE ZONE 최소 개수 구하기

접근법

• 관찰하기
  • 각 칸에는 이동할 수 있는 방향이 정해져있다.
  • 즉, 이미 경로는 정해져 있다는 것이다.
  • 그러면 이동 가능한 경로는 정해져 있고, 해당 경로에 SAFE ZONE을 설치해야한다.
  • 입력이 아래와 같이 주어졌을 때
    D L L L
    D R L U
    R R R U
  • 각 칸을 노드로 생각하고 간선을 이어보았다.

    

    직접, 간선을 이어보니 이동 가능한 경로가 더 명확했고, 결국 연결요소 개수만 구한다면 그게 곧 필요한 최소한의 SAFE ZONE 개수가 될 거라고 판단했다.
    
    • 즉, 저기 경로 안에 아무 칸에 하나씩 설치하면 무조건 이동이 가능하다.
    • 위 그림에서는 연결요소가 2개 이므로 최소 2개의 SAFE ZONE만 있으면 된다.
• 팁
  • 이번 문제는 2차원으로 주어져서 노드 번호를 1차원으로 펼쳐야했다.
    • 노드번호를 i*M + j + 1로 계산 해서 부여했다. (i : 행 번호, j : 열 번호)

코드

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

public class Main {
    static int N, M;
    static char[][] map;
    static int[] parent;

    static int find(int x) {
        if (parent[x] == x) return x;

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

    static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a == b) return;

        parent[b] = a;
    }

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

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        map = new char[N][M];

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

        String input;
        for (int i = 0; i < N; i++) {
            input = br.readLine();

            for (int j = 0; j < M; j++) {
                map[i][j] = input.charAt(j);
            }
        }

        // 연결 요소 만들기
        // 노드 번호 => i*M + j + 1;
        char dir;
        int v1, v2;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                dir = map[i][j];
                v1 = i * M + j + 1; // 현재 칸을 노드번호로 치환

                // 문제에서 지도를 벗어나는 경로는 주어지지 않는다 했으므로 경로 체크 X
                // 입력값에따라 다음 이동할 칸의 노드 번호 출력
                if (dir == 'U') v2 = (i - 1) * M + j + 1;
                else if (dir == 'D') v2 = (i + 1) * M + j + 1;
                else if (dir == 'L') v2 = i * M + (j - 1) + 1;
                else v2 = i * M + (j + 1) + 1;

                if (find(v1) == find(v2)) continue;

                // 같은 연결요소로 묶기
                union(v1, v2);
            }
        }

        // 연결요소 개수 구하기
        Set<Integer> set = new TreeSet<>();
        for (int i = 1; i <= N * M; i++) {
            set.add(find(i));
        }

        bw.write(String.valueOf(set.size()));
        bw.flush();
        bw.close();
        br.close();
    }
}