[백준/JAVA] 16946번: 벽 부수고 이동하기 4

📖 문제

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

 

 

 

💡  풀이 방식

• BFS

필요 자료구조
- 2차원 int형 배열 group : 0끼리 그룹화된 배열 정보 저장
- Map<그룹 번호, 해당 그룹에 속한 0 수> ⇒ 각각 다른 그룹으로 나눌 수 있다 (서로소 = 분리 집합)

 

- BFS 통해 그룹 생성 시, 이미 만들어진 그룹에 속한 인덱스는 제외하고 탐색을 진행한다.

- 벽(1)인 경우에만 본인 칸과 주변 상하좌우에 존재하는 0의 개수를 센다. (BFS 아니고 탐색 단 한 번)

 

 

 

 

💥 유의사항

N과 M이 각각 최대 1000이므로 BFS를 여러번 돌리면 시간 초과가 뜬다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    
    static int N,M;
    static int[][] map, group;
    
    static Map<Integer, Integer> groupSize = new HashMap<>();   // 🔔 (그룹 번호, 그룹에 속한 0의 수)
    
    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 int[N][M];
        group = new int[N][M]; // 🔔 속한 그룹 정보 저장용 배열
        
        for(int i = 0 ; i < N ; i++) {
            String str = br.readLine();
            for(int j = 0 ; j < M ; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        
        // 🔔 각 그룹마다 다른 key 갖게 함 (서로소, 분리 집합)
        int groupCnt = 1;
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(map[i][j] == 0 && group[i][j] == 0) { // 벽이 아니고, 그룹이 결정되지 않은 칸에 대해 bfs 수행
                    groupSize.put(groupCnt, bfs(i, j, groupCnt));
                    groupCnt++;
                }
            }
        }
        
        print();
    }
    
    // 벽에 맞닿은 그룹 합 계산 함수
    private static int count(int x, int y) {
        int cnt = 1; // 본인 칸 포함
        if(map[x][y] == 0)  return 0;
        
        Set<Integer> set = new HashSet<>(); // 현재 칸과 맞닿은 그룹 수 저장용 Set
        
        for(int d = 0 ; d < 4 ; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];
            
            if(!inRange(nx, ny) || group[nx][ny] == 0)  continue;
            
            // 맞닿은 그룹이 중복일 경우를 위해 Set에 저장
            set.add(group[nx][ny]);
        }
        
        for(int size : set) {
            cnt += groupSize.get(size);
        }
        
        return cnt % 10;
    }
    
    // 그룹마다 0이 몇 개인지 확인하는 메소드
    private static int bfs(int x, int y, int groupCnt) {
        int cnt = 1;
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{x, y});
        group[x][y] = groupCnt; // 그룹 번호 지정
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 4 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                // 격자 범위 내에 있고, 그룹에 속해 있지 않고, 벽이 아니어야 이동 가능
                if(canGo(nx, ny)) { // 
                    group[nx][ny] = groupCnt;   // 그룹에 속하게 하기
                    cnt++;
                    q.add(new int[]{nx, ny});
                }
            }
        }
        
        return cnt;
    }
    
    // 격자 범위 내에 있고, 그룹에 속해 있지 않고, 벽이 아니어야 이동 가능
    private static boolean canGo(int x, int y) {
        return (inRange(x, y) && group[x][y] == 0 && map[x][y] == 0);
    }
    
    private static boolean inRange(int x, int y) {
        return (0 <= x && x < N && 0 <= y && y < M);
    }
    
    // 출력 함수
    private static void print() {
        StringBuilder sb = new StringBuilder();
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                if(group[i][j] == 0)  {
                    sb.append(count(i, j)+"");
                    continue;
                }
                sb.append(0+"");
            }
            sb.append("\n");
        }
        
        System.out.println(sb.toString());
    }
}
 

 

 

 

---

💦 어려웠던 점

- N과 M의 크기가 1000이나 되므로 벽에서마다 bfs를 수행하면 시간초과가 당연히 뜰 것이라고 생각해야 했는데 그러지 못 했다. 개선하자!

 

 

🧐 새로 알게 된 내용

⭐ 분리 집합 : BFS 비용 최소화를 위해 그루핑을 먼저 진행하는 것 (참고)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

✔ 상세한 그림을 포함한 설명들 덕분에 이해하는 시간을 단축할 수 있었다. 감사합니다!!

[백준 16946] 벽 부수고 이동하기 (java)

 

[백준/자바] 16946 벽 부수고 이동하기 4