알고리즘 풀이 - 백준 16946(벽 부수고 이동하기 4, 그래프(BFS))

 

관련글

 

그래프 관련 포스팅은 여기를 참조
DFS 관련 포스팅은 여기를 참조
BFS 관련 포스팅은 여기를 참조

관련 문제인 벽 부수고 이동하기 관련 포스팅은 여기를 참조
관련 문제인 벽 부수고 이동하기2 관련 포스팅은 여기를 참조
관련 문제인 벽 부수고 이동하기3 관련 포스팅은 여기를 참조

 

 

1. 개요

 

문제의 링크는 여기를 참조

 

문제의 내용은 아래의 더보기를 클릭하여 참조

 

NxM의 맵에서 0은 이동 가능, 1은 벽일 때, 벽이 있는 모든 위치에서 벽을 부수어 이동 시 각 위치에서 이동 가능한 블록의 개수를 행렬의 결과로 구하는 문제

 

 

2. 풀이

 

이 문제를 그대로 이해해서 벽으로 표시된(1로 표시된) 모든 위치를 찾아서 각 위치에서 모두 BFS를 수행하여 풀고자 할 수 있다.

다만 그렇게 하면 시간이 너무 오래 걸린다. 따라서 다른 방식으로 해결해야 한다.

 

모든 빈 칸의 위치를 그룹으로 지정할 수 있다. 예를 들어 아래의 경우를 보자.(예제 2의 경우를 예시로)

 

스케치 표시된 곳은 벽이며 나머지 숫자가 표시된 곳은 빈 칸이다. 빈 칸들을 각각 인접한 것들은 모두 같은 번호로 묶어 하나의 그룹으로 만들었다.

이렇게 하면 각 그룹별로 이동 가능한 빈칸의 개수는 다음과 같이 정리된다.

각 그룹별 이동 가능 위치 수 : [2, 3, 1, 1, 1, 1]

 

이 때, 모든 벽의 위치에서 시작하여 주변에 인접한 서로 다른 그룹의 이동 가능 위치 수를 모두 더하면 결과를 구할 수 있다.

 

Logic은 다음과 같다.

① BFS를 통해 모든 빈 칸의 위치를 각각의 그룹으로 묶고 각 그룹 별 인접 위치 수를 저장한다.
② 모든 벽의 위치에서 시작하여 주변의 서로 다른 그룹의 이동 가능 위치 수를 더한다.
③ 결과를 출력한다.

 

 

3. 코드

 

아래의 코드를 통해 정답을 알아보자.

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

public class Main{
    static int n;
    static int m;
    static int[][] map;
    static int[][] district;
    static HashMap<Integer, Integer> hm;
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, -1, 0, 1};
    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 정보 저장
        map = new int[n][m];
        for(int i=0; i < n; i++){
            String s = br.readLine();
            for(int j=0; j < m; j++){
                map[i][j] = s.charAt(j) - '0';
            }
        }


        // 아래에서는 각 벽이 아닌 위치에서 인접 이동 가능 구역 개수, 구역 번호를 지정함
        district = new int[n][m];  // 각 구역이 표시된 2차원 배열
        
        // 반드시 해시맵으로 구현할 필요는 없다. 여기서는 그냥 편의상 사용해봤다.
        hm = new HashMap<>();
        int no = 1; // 구역 번호

        for(int i=0; i < n; i++){
            for(int j=0; j < m; j++){
                if(map[i][j] == 1 || district[i][j] != 0) continue;
                
                // 각 그룹의 이동 가능 위치 수를 더하여 넣고, 구역 번호를 1 더한다.
                hm.put(no, bfs(i, j, no++));
            }
        }

        // 각 벽의 위치에서 인접한 구역들의 이동 가능 개수를 찾음
        // 서로 다른 구역의 경우에만 모두 더해야 한다.
        StringBuilder sb = new StringBuilder();
        for(int i=0; i < n; i++){
            for(int j=0; j < m; j++){
                if(map[i][j] == 1){
                
                    // Set을 통해 현재 벽의 위치의 인접 그룹들이 중복되어 들어가지 않도록 조치한다.
                    HashSet<Integer> used = new HashSet<>();
                    int ans = 1;
                    for(int k=0; k < 4; k++){
                        int ny = i + dy[k];
                        int nx = j + dx[k];

                        // 범위를  벗어났거나 위치가 벽이라면 넘어간다.
                        if(ny < 0 || ny >= n || nx < 0 || nx >= m || map[ny][nx] != 0) continue;
                        
                        // 해당 위치의 구역을 구한다.
                        int d = district[ny][nx];
                        
                        // 이미 체크한 구역 그룹이 아닌 경우 추가한다.
                        if(!used.contains(d)){
                            used.add(d);
                            ans += hm.get(d);
                        }
                    }
                    sb.append(ans % 10);
                } else{
                    sb.append(0);
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    private static int bfs(int i, int j, int no){
        Queue<Integer> q = new LinkedList<>(); // 벽이 아닌 위치를 넣어 탐색하는 Queue
        q.offer(i * m +j );
        district[i][j] = no;

        int cnt = 1;
        while(!q.isEmpty()){
            int num = q.poll();
            int y = num / m;
            int x = num % m;

            for(int k=0; k < 4; k++){
                int ny = y + dy[k];
                int nx = x + dx[k];
                if(ny < 0 || ny >= n || nx < 0 || nx >= m || map[ny][nx] == 1) continue;
                if(district[ny][nx] == 0){
                    district[ny][nx] = no;
                    q.offer(ny * m + nx);
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

 

읽어주셔서 감사합니다. 오류가 있으면 지적해주시면 반영하겠습니다.