[백준] 16946번 : 벽 부수고 이동하기 4 - 자바(Java)

Problem 🔒

문제

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

 

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

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

출력

맵의 형태로 정답을 출력한다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

예제 입력 1

3 3
101
010
101

예제 출력 1

303
050
303

예제 입력 2

4 5
11001
00111
01010
10101

예제 출력 2

46003
00732
06040
50403

---

Approach ⭕

1. 빈 칸(0)에서 BFS를 돌려 빈 칸의 개수를 센다.
2. 해당 위치에서 이동할 수 있는 모든 빈 칸에 개수를 저장한다.
3. 그룹을 나누기 위해 그룹마다 인덱스를 생성하여 저장한다.
4. 벽(1)을 방문해 4방향 탐색하여 이동가능한 칸 수, 인덱스를 저장한다.
5. 중복되는 인덱스를 제외하고, 이동가능한 칸 수를 합하여 10으로 나눈다.

Solution Process 📝

1. BFS 실행
   • BFS 1번으로 이동할 수 있는 빈 칸의 개수를 구하여 저장까지 진행한다.
   • 큐를 2개 생성하여, 큐1으로 빈 칸의 개수를 구하고, 큐2로 저장한다.
   • 큐1을 빌 때까지 반복하며 이동할 수 있는 빈 칸이면 큐 2개에 좌표를 각각 추가하고, 개수를 증가시킨다.
   • 큐2를 빌 때까지 반복하며 구한 개수를 이동가능한 빈 칸에 저장한다.
2. 벽(1) 방문하여, 벽을 부수고 이동할 수 있는 칸의 개수를 세기
   • 빠르게 출력하기 위해 StringBuilder에 결과 값을 저장한다.
   • 4방향 탐색하며, arr[4][2]의 0번 열에 그룹번호, 1번 열에 빈 칸 개수를 저장한다.
   • HashSet을 활용하여, HashSet에 그룹번호가 없으면 추가하고, list에 {그룹번호, 빈 칸 개수} 배열을 저장한다. (중복된 그룹 제거 과정)
   • list에 있는 요소를 순회하며 빈 칸 개수를 더하여 10으로 나눈 값을 StringBuilder에 저장한다.

알게된 점 😯

static으로 Queue, HashSet, ArrayList를 선언으로 올린 후 메모리가 확연하게 줄었다.

반복적으로 변수, 자료구조 등을 선언하는 것은 메모리 소비가 많았다.

---

Solution 💡

public class 벽뿌4 {
    // cost : 이동할 수 있는 칸 개수 저장, id : 그룹 인덱스 저장
    static int N, M, map[][], cost[][], id[][], visit[][];
    static int[] dr={-1,1,0,0}, dc={0,0,-1,1};
    static Queue<int[]> q1 = new LinkedList<>(), q2 = new LinkedList<>();
    static HashSet<Integer> hs = new HashSet<>();
    static ArrayList<int[]> list = new ArrayList<>();
    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 = new int[N][M]; cost = new int[N][M]; id = new int[N][M]; visit = 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';
            }
        }
        // 0이면 BFS 실행
        int idx = 1;
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(map[i][j]==0 && visit[i][j]!=1){
                    BFS(i,j,idx++);
                }
            }
        }
        // 벽(1)인곳 방문해서 답 구하기
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                // 빈 칸(0)이면 그대로 sb에 추가
                if(map[i][j]==0){sb.append("0");}
                else{
                    int[][] arr = new int[4][2]; // 0:idx, 1:cost
                    // 4방향 탐색하며, 그룹번호와 빈 칸 개수 저장
                    for(int d=0; d<4; d++){
                        int nr = i + dr[d];
                        int nc = j + dc[d];
                        if(nr>=0 && nr<N && nc>=0 && nc<M){
                            arr[d][0] = id[nr][nc]; // 그룹번호
                            arr[d][1] = cost[nr][nc]; // 빈 칸 개수
                        }
                    }
                    hs.clear();
                    list.clear();
                    // 중복된 그룹 제거과정
                    for(int[] row : arr){
                        // hashset에 그룹번호가 없으면
                        if(!hs.contains(row[0])){
                            hs.add(row[0]); // hashset에 그룹번호만 추가하고
                            list.add(row); // list에 {그룹번호, 빈 칸개수} 배열 저장
                        }
                    }
                    int ans = 1;
                    for(int[] get : list){
                        ans+=get[1];
                    }
                    sb.append(ans%10);
                }
            }
            sb.append("\\n");
        }
        System.out.println(sb);
    }
    public static void BFS(int r, int c, int i){
        visit[r][c] = 1;
        q1.add(new int[]{r,c});
        q2.add(new int[]{r,c});
        int cnt = 1; // 이동 가능한 빈 칸 개수
        // q1을 반복하며 빈 칸의 개수를 구한다.
        while(!q1.isEmpty()){
            int[] cur = q1.poll();
            for(int d=0; d<4; d++){
                int nr = cur[0] + dr[d];
                int nc = cur[1] + dc[d];
                // 이동할 수 있는 빈 칸이면 큐2개에 좌표를 각각 추가하고, 개수를 증가시킨다.
                if(nr>=0 && nr<N && nc>=0 && nc<M && visit[nr][nc]==0 && map[nr][nc]==0){
                    cnt++;
                    visit[nr][nc]=1;
                    q1.add(new int[]{nr,nc});
                    q2.add(new int[]{nr,nc});
                }
            }
        }
        // q2를 반복하며 구한 빈 칸의 개수(cnt)를 이동가능한 빈 칸에 저장한다.
        while(!q2.isEmpty()){
            int[] get = q2.poll();
            cost[get[0]][get[1]] = cnt;
            id[get[0]][get[1]] = i;
        }
    }
}