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

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

 

문제분석

문제 설명이 불친절하다는 생각이 든다. 4번째 문제여서 그런지 모르겠지만, 이 문제로 시리즈를 처음 접한 사람은 당황스러울수도 있을 것 같다. 예제 입력과 출력으로 유추한 내용은, 맵을 주어주고, 1이 써진 칸들의 주변 상하좌우 4칸으로 갈 수 있는 최대 빈칸+1을 해당 1이 써저있는 위치에 적어놓을 것, 이다. 이 설명보다는 예제 입력과 출력을 보면 이해가 쉬울 것이다.

 

 

구현을 위해 여러 자료구조를 사용하였다. 시간 복잡도를 낮추기 위해 중첩 for문을 한번만 사용하도록 구현하였다. 방법은 다음과 같다.

1. 0이 이어진 공간들을 '영역' 이라고 칭한다.

2. 영역 번호와 영역 넓이를 저장해놓는다.

3. 1인 위치의 값을 업데이트할 때, 주변 상하좌우4칸의 영역 번호를 set에 저장한 뒤(중복방지), 2에서 저장한 영역 넓이를 더한다.

 

영역을 0번, 1번...5번 까지 지정하고, Map으로 영역 번호와 넓이를 저장해둔다. [0][0]은 영역번호 0과 1을 더한 뒤, 1을 더해서 결과값 6을 도출한다.

 

해결과정

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

public class Main {
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] mapArr = new int[N][M];
        boolean[][] visited = new boolean[N][M];
        int[][] areaArr = new int[N][M]; // 해당 위치가 어느 영역에 해당하는지 '영역숫자'를 저장하기 위함. -1일경우 할당안됨.
        Map<Integer,Integer> areaMap = new HashMap<Integer,Integer>(); // 영역숫자와 영역크기 map


        for(int i=0; i<N; i++){
            Arrays.fill(visited[i],false);
            Arrays.fill(areaArr[i],-1);
            String s = br.readLine();
            for(int j=0; j<M; j++){
                mapArr[i][j]=s.charAt(j)-'0';
            }
        }

        
        // 위, 아래, 왼쪽, 오른쪽 탐색(확인)위해 DR,DC 인덱스 0 ~ 3 까지 탐색하면 됨.
        int[] NR = {-1, 1, 0, 0};   
        int[] NC = {0, 0, -1, 1};

        ArrayDeque<Integer> stack = new ArrayDeque<>(); // DFS나 BFS나 같은 결과
        int areaNum = 0;

        ArrayList<Integer> idxList = new ArrayList<Integer>(); // mapArr에서 1이 저장된 부분만 저장 (row*M+col)
        
        // 영역숫자-영역넓이 구하기 위함
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(mapArr[i][j]==1){
                    idxList.add(i * 1001 + j);
                }

                if(mapArr[i][j] == 0 && !visited[i][j]){ // 0의로 이루어진 영역들을 탐색하기 위함

                    stack.push(i * 1001 + j);
                    int count = 1;

                    while(!stack.isEmpty()){
                        int idx = stack.pop();
                        int row = idx/1001;
                        int col = idx%1001;
                        
                        visited[row][col] = true;
                        areaArr[row][col] = areaNum;

                        for(int dir = 0; dir<4; dir++){
                            int nRow = row + NR[dir];
                            int nCol = col + NC[dir];

                            if(nRow>=0 && nRow < N && nCol>=0 && nCol < M && !visited[nRow][nCol] && mapArr[nRow][nCol] == 0){ // 이어진 0인 경우
                                count++;
                                visited[nRow][nCol]=true;
                                areaArr[nRow][nCol] = areaNum;
                                stack.push(nRow * 1001 + nCol);
                            }
                        }
                    }
                    areaMap.put(areaNum,count); // areaNum와 count map에 더하기
                    areaNum++;
                }

            }
        }
        Set<Integer> set= new HashSet<Integer>();
        for(int i = 0; i<idxList.size(); i++){
            int idx = idxList.get(i);
            int row = idx/1001;
            int col = idx%1001;
            for(int dir = 0; dir<4; dir++){
                int nRow = row + NR[dir];
                int nCol = col + NC[dir];
                if(nRow>=0 && nRow < N && nCol>=0 && nCol < M && areaArr[nRow][nCol]!=-1){
                    set.add(areaArr[nRow][nCol]);
                }
            }
            int count = 0;
            for(int area : set){
                count+=areaMap.get(area);
            }
            set.clear();
            mapArr[row][col] = (1 + count)%10;
        }


        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                bw.write(String.valueOf(mapArr[i][j]));
            }
            bw.newLine();
        }
        
        bw.flush();
        bw.close();
    }
}