💔벽 부수고 이동하기 4

 

1. 문제 설명

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

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

www.acmicpc.net

벽이 부분을 부수고 거기서 이동할 수 있는 공간의 크기를 구하라. 원래 부터 0이었던 공간은 그냥 0으로 출력, 원래 1(벽)이었던 공간은 그 벽을 부수고 좌우로 최대한 이동할 수 있는 공간의 개수를 해당 자리에 출력

2.문제 푸는 원리

처음엔 벽 하나하나 마다, 그 자리를 부수고, bfs를 돌렸다. 이렇게 풀었더니 시간초과가 났다. 다른 방법이 생각나지 않아서 다른 사람이 푼 원리를 읽었다. 내가 시간초과가 났던 이유는, 모든 1에서 bfs를 돌렸기 때문이다. 이러한 시간을 줄이기 위해서는, 미리 0이 연속된 공간의 개수와 해당 공간의 크기를 미리 세어서 hashMap에 저장해둔다. 그리고 다시 그래프 1인 부분에서 4방 탐색만 해서, 0군집 중 어느 것과 만나는지 확인한다. 그림으로 표현하면 다음과 같다.

벽 부분에서 4방 탐색해서 어떤 0의 군집과 만나는지만 확인하면, 그 군집의 방의 개수를 더해서 해당 벽에서 갈 수 있는 공간을 구할 수 있다. 주의할 점은 4방 탐색을 할 때, 해당 군집을 방문 했는지 방문 체크를 해야한다는 것이다. 이유는 다음과 같다.

3. 코드 분석

Copy

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

public class Main{

    // 그래프의 가로 세로
    static int N;
    static int M;

    // 군집한 것 숫자 세는 용
    static int uniNum = 2;

    static int [][] graph;
    static int [][] union;


    // <0군집의 번호, 0군집 내의 개수>
    static HashMap<Integer, Integer> map = new HashMap<>();

    // 쓴 유니온 집합 확인 용
    static BitSet bit;


    static int [] idx = {-1,0,1,0};
    static int [] idy = {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());

        graph = new int[N][M];
        union = new int[N][M];


        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                graph[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }

        // 유니온 군집 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                // 원 그래프에서 해당 부분이 0이고, 0군집 세는 곳에서도 아직 체크가 안되었다면
                if(graph[i][j] == 0 && union[i][j] == 0){
                    zeroBfs(i,j);
                }
            }
        }

//        System.out.println(map);
//

        StringBuilder sb = new StringBuilder();

        // 이제 1인 지점에서 사방 탐색해서 유니온 몇 개인지만 세면 된다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(graph[i][j] == 1){
                    sb.append(check4(i,j));
                }
                else{
                    sb.append(0);
                }
            }
            sb.append("\n");
        }

        System.out.println(sb);


    }

    // BFS 0 군집용 -> 원 그래프에서 0이 아닌 지점 확인 -> 거기서 군집부분을 전부 숫자로 바꿈.
    static void zeroBfs (int x, int y) {
        ArrayDeque<Coordinate127> aq1 = new ArrayDeque<>();
        aq1.add(new Coordinate127(x,y));
        union[x][y] = uniNum;
        int cnt = 0;
        while(!aq1.isEmpty()){
            int Qsize = aq1.size();

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

                Coordinate127 now = aq1.poll();

                for (int j = 0; j < 4; j++) {
                    int nx = now.x + idx[j];
                    int ny = now.y + idy[j];

                    if(nx >= 0 && ny >= 0 && nx < N && ny < M){
                        if(union[nx][ny] == 0 && graph[nx][ny] == 0){
                            union[nx][ny] = uniNum;
                            aq1.add(new Coordinate127(nx,ny));
                        }
                    }
                }

                cnt++;
            }
        }
        map.put(uniNum, cnt);
        uniNum++;
    }

    static int check4 (int x, int y) {
        int ans = 1;
        bit = new BitSet(uniNum);

        for (int i = 0; i < 4; i++) {
            int nx = x + idx[i];
            int ny = y + idy[i];

            if(nx >= 0 && ny >=0 && nx < N && ny < M){
                int nowUnion = union[nx][ny];
                if(nowUnion == 0) continue;
                // 만약 현재 조회중인 0 군집을 아직 확인하지 않은 상태라면,
                if(!bit.get(nowUnion)){
                    bit.set(nowUnion, true);
                    ans += map.get(nowUnion);
                }
            }
        }

        return ans%10;
    }

}

class Coordinate127 {
    int x;
    int y;

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