문제

벽 부수고 이동하기4

문제 접근

처음에는 부술 벽을 정한 뒤 그 벽을 부수는 방법으로 접근을 했다. 부술 벽이 많게 된다면 시간초과가 뜰거 같지만 일단 시도는 해봤다. 역시나 시간초과가 나왔다.
그래서 두번째로 n*m만큼 system.out.println을 찍어서 이것을 StringBuilder를 이용하여 한번에 출력을 했다. 이 방법도 역시나 마찬가지로 시간초과가 나왔다.
그래서 아예 0들의 그룹의 크기를 정해서 벽의 인접한 칸 그룹들의 이동가능한 값들을 모두 더하기로 했다.

1. 0들의 그룹의 크기를 미리 정해준다.

예시
11001
00111
01010
10101 

groupCnt[] = { 0, 2, 3 , 1 , 1 , 1, 1 ...};
group[][] 
-> 00110
   22000
   20304
   05060

2. 그런 다음 벽의 인접한 칸들의 그룹들을 구한다. 이때에 중복처리를 위해 Set을 이용했다.
3. StringBuilder를 이용하여 한번에 출력

정답코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main { //16946

    static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};

    /**
     * 시간초과
     * 1. 값이 나올때마다 sout 출력을해서 -> StringBuiler로 변경하여 한번에 출력
     * 2. 부술 벽을 정한 뒤 그 벽을 부수는 방법이 비효울적이다
     * 3. 벽이 아닌 0들의 그룹의 크기를 미리 저장하여 벽의 상하좌우의 인접한 칸에서 미리저장된 값들을 사용

     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int board[][] = new int[n][m];
        int group[][] = new int[n][m];

        for (int i = 0; i < n; i++) {
            String s[] = br.readLine().split("");

            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.parseInt(s[j]);
            }
        }

        int groupId = 1;
        int []groupCnt = new int[ (n * m)+1];
        boolean visited[][] = new boolean[n][m];
        //0인 부분의 그룹 체크
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j]==0 && !visited[i][j])
                {
                    groupCnt[groupId] = doGroupZero(i,j,n,m,group,board,groupId,visited);
                    groupId++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        //벽과 인접한 칸의 그룹 ID check 후 이동가능한 칸 구하기
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(board[i][j] == 1)
                {
                    //자기 자신의 자리
                    int sumv = 1;
                    //인접한 칸의 그룹 탐색
                    Set<Integer> set = new HashSet<>();
                    for(int d=0;d<4;d++)
                    {
                        int nx = i+dx[d];
                        int ny = j+dy[d];

                        if( 0<= nx && nx<n && 0<= ny && ny<m )
                        {
                            if(board[nx][ny] == 0)
                            {
                                int groupNumber = group[nx][ny];
                                if(set.contains(groupNumber))continue;
                                set.add(groupNumber);
                                sumv += groupCnt[groupNumber];
                            }
                        }
                    }

                    sb.append(sumv % 10);
                }
                else {
                    sb.append(0);
                }
            }
            sb.append("\n");
        }

        System.out.println(sb.toString());
    }

    private static int doGroupZero(int x, int y,int n, int m,int[][]group, int[][] board, int groupId, boolean [][]visited) {
        Queue<int[]> queue = new LinkedList<>();
        int count = 1;
        group[x][y] = groupId;
        queue.add(new int[]{x,y});
        visited[x][y] = true;

        while(!queue.isEmpty())
        {
            int cnt[] = queue.poll();

            for(int i=0;i<4;i++)
            {
                int nx = cnt[0] + dx[i];
                int ny = cnt[1] + dy[i];

                if( 0<= nx && nx < n && 0<= ny && ny < m )
                {
                    if(!visited[nx][ny] && board[nx][ny] == 0)
                    {
                        queue.add(new int[]{nx,ny});
                        count++;
                        visited[nx][ny] = true;
                        group[nx][ny] = groupId;
                    }
                }
            }

        }
        return count;
    }
}