[자바] 백준 22956 - 소나기 (java)

목차

문제 : boj22956

 

 

필요 알고리즘

• 분리 집합 (union-find)
  
  • 분리 집합을 활용해 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  이 문제를 풀기위해 알 수 있어야 하는건 말로하면 간단하다. 인접한 비가 내렸었던 땅들의 그룹들이 있다. 그리고 어딘가 비가 내렸다면, 상하좌우 인접한 비가 내렸던 땅들의 그룹을 합친다. 그리고 그 그룹들에서 가장 높이가 낮은 칸 또는 여러개라면 그 중 가장 오래된 칸을 '빠르게'알 수 있으면 된다.

 

  뭔가 분리된 그룹들을 만들어서 그 그룹내의 정보를 파악하는 문제이므로, 우선 분리 집합으로 접근해보면 좋을 것 같다고 생각했고, 이론상 문제 없어보여서 분리 집합으로 진행했다. 약간의 케이스들이 있어서 그 부분만 잘 처리해주면 어렵지 않은 분리 집합 문제인 것 같다. 해결한 방식은 그냥 여러 개의 분리된 집합을 유지하면서, 해당 집합 중 가장 낮은 위치 혹은 그런게 여러개면 가장 오래된 위치를 기록할 수 있게 하는 것이다.

 

 

1. 비가 이미 왔던 곳에 다시 비가 내린 경우

-> 이미 이전에 비가 내렸을 때 땅을 연결해줬을테니  이 경우 주변 그룹들과 연결하는 과정을 해줄 필요는 없다. 그냥 현재 비가 내린 곳이 속한 그룹 내에서 가장 낮은 지점보다, 현재 비가 온 지점이 더 낮다면 해당 그룹의 정답 데이터를 교체해주면 된다.

if (map.containsKey(num)) {
    int[] tmp = map.get(num);
    if (tmp[2] > arr[a][b]) {
        tmp = new int[]{a, b, arr[a][b], q};
    }

    map.put(num, tmp);
    sb.append(tmp[0]+1).append(' ').append(tmp[1]+1).append('\n');

    continue;
}

 

 

2. 처음으로 비가 온 지점인 경우

-> 이 경우 상하좌우로 인접한 땅들과 현재 지점을 합쳐주는 과정이 필요하다. 이 때 그룹이 이하처럼 4개로 되어 있었고, 이번에 비가 온 지점이 '*' 위치라고 해보자. 그럼 여러 그룹들이 합쳐지면서 총 4개의 그룹 및 현재 비가온 지점 전체 중 가장 위치가 낮거나, 오래된 지점을 찾을 수 있어야 한다. 이 부분만 주의해서 구현해주면 된다.

for (int d = 0; d < 4; d++) {	// 상하좌우 인접한 지점을 보면서
    int nr = a+DR[d];
    int nc = b+DC[d];
    if (nr>=r||nr<0||nc>=c||nc<0) continue;
    int adjNum = find(nr*c+nc);
    if (!map.containsKey(adjNum)) continue;	// 인접한 곳에 비가 안왔으면 무시

	// 이하 인접한 곳에 비가 온 그룹이 있으므로 합쳐줘야 하는 경우.
    int[] tmp1 = map.get(adjNum);
    int[] tmp2 = map.get(find(a*c+b));
    int[] tmp = tmp1;
    if (tmp1[2] > tmp2[2]) tmp = tmp2;
    else if (tmp1[2] < tmp2[2]) tmp = tmp1;
    else if (tmp1[3] > tmp2[3]) tmp = tmp1;
    else tmp = tmp2;

    union(num, adjNum);	// 분리 집합을 union 해주고
    map.put(find(a*c+b), tmp);	// 위에서 찾은 가장 낮거나 오래된 지점을 그룹에 새롭게 등록한다.
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
    private static final int[] DR = {-1, 0, 0, 1};
    private static final int[] DC = {0, -1, 1, 0};

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private int[] parents;
    Map<Integer, int[]> map = new HashMap<>();

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b || !map.containsKey(a) || !map.containsKey(b)) return;

        int hi = parents[a] < parents[b] ? a:b;
        int lo = parents[a] < parents[b] ? b:a;
        parents[hi] += parents[lo];
        parents[lo] = hi;
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        int q = Integer.parseInt(st.nextToken());
        parents = new int[r*c];
        Arrays.fill(parents, -1);

        int[][] arr = new int[r][c];
        for (int i = 0; i < r; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < c; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        StringBuilder sb = new StringBuilder();
        while (q-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            int reduce = Integer.parseInt(st.nextToken());
            int num = find(a*c+b);
            arr[a][b]-=reduce;

            if (map.containsKey(num)) {
                int[] tmp = map.get(num);
                if (tmp[2] > arr[a][b]) {
                    tmp = new int[]{a, b, arr[a][b], q};
                }

                map.put(num, tmp);
                sb.append(tmp[0]+1).append(' ').append(tmp[1]+1).append('\n');

                continue;
            }

            map.put(num, new int[]{a, b, arr[a][b], q});

            for (int d = 0; d < 4; d++) {
                int nr = a+DR[d];
                int nc = b+DC[d];
                if (nr>=r||nr<0||nc>=c||nc<0) continue;
                int adjNum = find(nr*c+nc);
                if (!map.containsKey(adjNum)) continue;

                int[] tmp1 = map.get(adjNum);
                int[] tmp2 = map.get(find(a*c+b));
                int[] tmp = tmp1;
                if (tmp1[2] > tmp2[2]) tmp = tmp2;
                else if (tmp1[2] < tmp2[2]) tmp = tmp1;
                else if (tmp1[3] > tmp2[3]) tmp = tmp1;
                else tmp = tmp2;

                union(num, adjNum);
                map.put(find(a*c+b), tmp);
            }

            int[] ans = map.get(find(a*c+b));
            sb.append(ans[0]+1).append(' ').append(ans[1]+1).append('\n');
        }
        System.out.print(sb);
    }
}