백준 16946 벽 부수고 이동하기4(JAVA)

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

16946번: 벽 부수고 이동하기 4

 

간만에 알고리즘을 푸려니까 잘 안된다

 

이 문제는 벽이 없는 구간들을 그룹화 하는게 중요하다. 

 

1	0	0	1
0	1	1	0
0	0	1	0
0	0	1	0

 

위와 같은 인풋이 들어오면 다음과 같이 그룹화해준다.

 

1	10	10	1
11	1	1	12
11	11	1	12
11	11	1	12

각각을 그룹화 한 다음 Map에 그 그룹이 몇개인지 저장한다.

 

그룹 10 : 2

그룹 11 : 5

그룹 12 : 3

 

이제 준비작업은 끝났다. 이 준비작업을 하는 함수가 Init()이다.

 

이제 주어진 인풋 전체를 돌면서 1을 만나면 상하좌우 그룹의 개수를 더해준다.

 

1 : 그룹 10이 2개 그룹 11이 5개여서 총 7개	10	10	1
11	1	1	12
11	11	1	12
11	11	1	12

 

이런 식으로 하면 된다.

 

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

public class Main {

    static class Pair {
        int r, c;

        Pair(int a, int b) {
            r = a;
            c = b;
        }
    }

    static int N;
    static int M;
    static int[][] map;
    static int[][] result;
    static int[] dr = {-1, 0, 1, 0};
    static int[] dc = {0, 1, 0, -1};
    static Map<Integer, Integer> indexMap = new HashMap<>();

    static int pI(String s) {
        return Integer.parseInt(s);
    }

    static boolean isRange(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < M;
    }

    static void init(int r, int c, int index) {
        Queue<Pair> q = new LinkedList<>();
        q.add(new Pair(r, c));

        map[r][c] = index;

        int sum = 1;

        while (!q.isEmpty()) {
            int cr = q.peek().r;
            int cc = q.poll().c;

            for (int i = 0; i < 4; i++) {
                int nr = cr + dr[i];
                int nc = cc + dc[i];
                if (isRange(nr, nc) && map[nr][nc] == 0) {
                    map[nr][nc] = index;
                    sum++;
                    q.add(new Pair(nr,nc));
                }
            }
        }
        indexMap.put(index, sum);
        return;
    }

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

        N = pI(st.nextToken());
        M = pI(st.nextToken());
        map = new int[N][M];
        result = new int[N][M];

        for (int i = 0; i < N; i++) {
            int c = 0;
            st = new StringTokenizer(br.readLine());
            String[] s = st.nextToken().split("");
            for (String str : s) {
                map[i][c++] = pI(str);
            }
        }

        /* Mapping */
        int index = 10;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    init(i, j, index++);
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 1) {
                    HashSet<Integer> used = new HashSet<>();

                    int sum = 1;

                    for (int k = 0; k < 4; k++) {
                        int nr = i + dr[k];
                        int nc = j + dc[k];
                        if (isRange(nr, nc) && !used.contains(map[nr][nc]) && map[nr][nc] != 1){
                            used.add(map[nr][nc]);
                            sum += indexMap.get(map[nr][nc]);
                        }
                    }
                    bw.write((sum%10) + "");
                } else {
                    bw.write("0");
                }
            }
            bw.write("\n");
        }
        bw.flush();
    }
}