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

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

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

이 문제에서는 배열 크기를 잘못 설정해줘서 런타임에러(ArrayIndexOutOfBounds)가 났다.

반례를 생각해내서 풀긴 했지만, 바로 생각해내지 못해서 글로 남겨본다.

import java.util.*;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] a = new int[n][m];

        for(int i=0; i<n; i++){
            String temp = sc.next();
            for(int j=0; j<m; j++){
                a[i][j] = temp.charAt(j) - '0';
            }
        }
        int[] dx = {-1,0,1,0};
        int[] dy = {0,1,0,-1};
        int[][] group = new int[n][m];
        int[] groupSize = new int[n*m+1];
        int groupCnt = 1;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j]==0 && group[i][j]==0){
                    int eachGSize = 0;
                    group[i][j] = groupCnt;
                    Queue<Integer> q = new LinkedList<>();
                    q.add(i);
                    q.add(j);
                    while(!q.isEmpty()){
                        int x = q.poll();
                        int y = q.poll();
                        eachGSize++;
                        for(int k=0; k<4; k++){
                            int nx = x + dx[k];
                            int ny = y + dy[k];
                            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                            if(a[nx][ny]==1 || group[nx][ny]!=0) continue;
                            group[nx][ny] = group[x][y];
                            q.add(nx); q.add(ny);
                        }
                    }
                    groupSize[groupCnt] = eachGSize%10;
                    groupCnt++;
                }
            }
        }

        int[][] ans = new int[n][m];
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                if(a[i][j]==1){
                    int acnt = 1;
                    Set<Integer> set = new HashSet<>();
                    for(int k=0; k<4; k++){
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if(a[nx][ny] == 1) continue;
                        if(set.add(group[nx][ny])){
                            acnt += groupSize[group[nx][ny]];
                        }
                    }
                    ans[i][j] = acnt%10;
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                sb.append(ans[i][j]);
            }
            sb.append("\n");
        }
        System.out.println(sb.toString());
    }

}

위와 같이 풀어서 통과했지만,

int[] groupSize = new int[n*m+1] 부분을 처음에는 int[] groupSize = new int[n*m] 으로 제출했었다.

 

런타임에러(ArrayIndexOutOfBounds)가 날만한 부분은

벽이 아닌 빈 공간을 그룹지었을 때 <int[그룹번호(그룹 개수)] = 그룹크기> 설정한 부분밖에 없는데..

(그룹의 개수 >= n*m )인 경우가 생각나지 않았다.

 

그룹은 벽이 아닌 칸들이 연결된 곳인데, n*m 개수만큼 그룹이 있을 수 없다고 생각했다가 반례가 생각났다.

n = 1, m = 1 이면서 맵의 값이 0 인 경우는, new int[n*m]은 index가 0 까지만 있는데 그룹의 개수는 1이 되어서 groupSize[1] 이라는 ArrayIndexOutOfBounds 에러가 나는 것이다!

 

그래서, int[] groupSize = new int[n*m+1] 부분을 아래와 같이 수정해주어도 통과했다.

int[] groupSize = new int[n*m == 1 ? 2 : n*m];

단, 사용하는 메모리는 살짝 줄었지만 시간은 늘었다.