[백준 16946] 벽 부수고 이동하기4 / 자바 / bfs or dfs(방향탐색)

#문제         

레벨: G2
알고리즘: bfs or dfs  
풀이시간: 1시간
힌트 참조 유무:

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

---

#문제 풀이        

처음에 문제를 보고 무슨소리인가 했다. 나와 같을 수도 있는 여러분들을 위해 쉽게 말해보겠다.

1에 위치해있을 때 바로 근처에 있는 0에게 갈 수 있다. 0을 가고나서는 근처 0까지 돌아다닐 수 있다. 즉, 우린 인접해 있는 0의 섬의 넓이와 개수를 구하면 되는 거다.

 

1. 전체를 순회하며 0의 섬에게 그룹네이밍으로 바꿔준다. ex) A, B, C, D ....  (구현에서는 숫자로 할거임) && 그룹네이밍과 넓이는 map에 저장한다

2. 다시 순회하며 1(벽)의 관점으로 근처에 어떤 섬이 있는 지 찾은 후 배열에 넣어둔다.

근처섬을 다 찾았다면 배열에 넣어둔 섬과 Map(Key: 섬 Value: 넒이)을 이용해 넓이들을 더해준다. 그 Sum으로 1 -> Sum 바꿔준다.    

 

 

---

#풀이 코드      

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

public class Main {
    static int N, M;
    static int[][] map;
    static int[][] group;
    static Map<Integer, Integer> groupSize = new HashMap<>();
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 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());

        map = new int[N][M];
        group = new int[N][M];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        int groupNum = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0 && group[i][j] == 0) {
                    bfs(i, j, groupNum++);
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 0) {
                    sb.append(0);
                } else {
                    Set<Integer> nearGroups = new HashSet<>();
                    int sum = 1;
                    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 && group[nx][ny] > 0) {
                            nearGroups.add(group[nx][ny]);
                        }
                    }
                    for (int g : nearGroups) {
                        sum += groupSize.get(g);
                    }
                    sb.append(sum % 10);
                }
            }
            sb.append("\n");
        }

        System.out.print(sb);
    }

    static void bfs(int x, int y, int groupNum) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        group[x][y] = groupNum;
        int count = 0;

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            count++;

            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                if (nx >= 0 && nx < N && ny >= 0 && ny < M && map[nx][ny] == 0 && group[nx][ny] == 0) {
                    queue.offer(new int[]{nx, ny});
                    group[nx][ny] = groupNum;
                }
            }
        }

        groupSize.put(groupNum, count);
    }
}

---

#비슷한 유형