🔗 Problem

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

👩‍💻 Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

// 벽 부수고 이동하기 4

public class BJ16946 {
    
    private static class Node {

        int x;
        int y;

        Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int n, m;
    static boolean[][] map;
    static boolean[][] visited;
    static int[][] group;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static HashMap<Integer, Integer> groupInfo = new HashMap<>();
    static Queue<Node> queue = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new boolean[n][m];
        visited = new boolean[n][m];
        group = new int[n][m];

        for(int i = 0; i < n; i++) {
            String line = br.readLine();
            for(int j = 0; j < m; j++) {
                if(line.charAt(j) == '1') map[i][j] = true;
            }
        }

        solution();
        System.out.println(sb.toString());
    }

    private static void solution() {

        int groupNum = 1;

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(!map[i][j] && group[i][j] == 0) {
                    int cnt = numOfAdj(i, j, groupNum);
                    groupInfo.put(groupNum++, cnt);
                }
            }
        }

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {

                int result = 0;
                if(map[i][j]) {
                    result = numOfPossible(i, j) % 10;
                }
                sb.append(result);
            }
            sb.append("\n");
        }
    }

    private static int numOfAdj(int r, int c, int groupNum) {

        int cnt = 1;
        queue.add(new Node(r, c));
        group[r][c] = groupNum;

        while(!queue.isEmpty()) {

            Node poll = queue.poll();

            for(int i = 0; i < 4; i++) {
       
                int xx = poll.x + dx[i];
                int yy = poll.y + dy[i];
                if(xx < 0 || xx >= n || yy < 0 || yy >= m) continue;

                if(!map[xx][yy] && group[xx][yy] == 0) {
                    queue.add(new Node(xx, yy));
                    group[xx][yy] = groupNum;
                    cnt++;
                }
            }
        }

        return cnt;
    }

    private static int numOfPossible(int r, int c) {

        int num = 1;
        HashSet<Integer> set = new HashSet<>();

        for(int i = 0; i < 4; i++) {

            int xx = r + dx[i];
            int yy = c + dy[i];

            if(xx < 0 || xx >= n || yy < 0 || yy >= m || group[xx][yy] == 0) continue;
            if(set.contains(group[xx][yy])) continue;
            set.add(group[xx][yy]);
        }

        for(Integer group : set) {
            num += groupInfo.get(group);
        }

        return num;
    }

}

📌 Note

아이디어

• 0인 칸 기준으로 bfs 돌려서 0인 그룹 찾기
• 각 그룹별 칸의 개수 groupInfo에 저장
• 1인 칸 기준 상하좌우 탐색해서 해당 그룹의 칸의 개수 합산

시간초과 발생

• 아이디어는 잘 생각해 냈는데 구현에 있어서 자료구조를 복잡하게 사용했다.
• 처음에 int[][] group 대신 group과 cnt를 담는 class를 생성하여 해당 class를 자료형으로 hashset을 사용했다. hashset을 탐색하는 과정에서 시간초과가 났고 대신 배열을 사용하니 해결된 듯 하다.