이번에 풀어본 문제는
백준 16946번 벽 부수고 이동하기 4 입니다.

📕 문제 링크

❗️코드

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

class Point
{
    int x,y;
    
    public Point(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}
public class Main {
    static int N,M;
    static int [][] map;
    static int [][] group;
    static List<Integer> groupArea;
    static boolean [][] visited;
    static Queue<Point> blank;
    static Queue<Point> wall;
    static int [] dx = {-1,1,0,0};
    static int [] dy = {0,0,-1,1};
    static int groupSize;
    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];
        groupArea = new ArrayList<>();

        blank = new LinkedList<>();
        wall = new LinkedList<>();

        for (int i = 0; i < N; ++i) {
            String tmp = br.readLine();

            for (int j = 0; j < M; ++j) {
                int next = tmp.charAt(j) - '0';
                map[i][j] = next;
                if (next < 1) blank.add(new Point(i, j));
                else wall.add(new Point(i, j));
            }
        }

        int groupNum = 0;
        visited = new boolean[N][M];

        // 빈칸 그룹화
        while (!blank.isEmpty()) {
            Point cur = blank.poll();
            if (visited[cur.x][cur.y]) continue;
            visited[cur.x][cur.y] = true;
            makeGroup(cur.x, cur.y, groupNum);
            groupNum++;
        }
        groupSize = groupArea.size();

        int [][] answer = new int[N][M];
        //벽 부수고 해당 인접한 그룹들의 값 더하기
        while (!wall.isEmpty()) {
            Point cur = wall.poll();
            answer[cur.x][cur.y] = getTotal(cur.x, cur.y) % 10;
        }

        StringBuilder sb = new StringBuilder();
        for(int [] i : answer)
        {
            for(int j : i) sb.append(j);
            sb.append("\n");
        }
        System.out.print(sb);
    }

    static void makeGroup(int i, int j,int groupNum)
    {
        Queue<Point> tmpQ = new LinkedList<>();
        tmpQ.add(new Point(i,j));
        int cnt = 0;
        while(!tmpQ.isEmpty())
        {
            Point cur = tmpQ.poll();

            group[cur.x][cur.y] = groupNum;
            cnt++;

            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || visited[mx][my] || map[mx][my] > 0) continue;

                visited[mx][my] = true;
                tmpQ.add(new Point(mx,my));
            }
        }
        groupArea.add(cnt);
    }


    static int getTotal(int i, int j)
    {
        Queue<Point> tmpQ = new LinkedList<>();
        tmpQ.add(new Point(i,j));
        int total = 1;

        boolean [] visitedGroup = new boolean[groupSize];
        while(!tmpQ.isEmpty())
        {
            Point cur = tmpQ.poll();

            for(int idx = 0; idx < 4; ++idx)
            {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if(!isValid(mx,my) || map[mx][my] > 0) continue;

                //방문하지 않았던 그룹이면 토탈에 더해줌.
                int groupNum = group[mx][my];
                if(visitedGroup[groupNum]) continue;
                total += groupArea.get(groupNum);
                visitedGroup[groupNum] = true;
            }
        }
        return total;
    }
    static boolean isValid(int x, int y)
    {
        return x >= 0 && y >= 0 && x < N && y < M;
    }
}

📝 풀이

각각 벽의 위치에서, 해당 벽을 부쉈을 때 인접한 빈칸으로 이동할 수 있는 칸수를 출력하는 문제입니다.
문제 설명이 조금 모호한데, 예제를 보면 이해할 수 있습니다.
처음엔 간단한 bfs문제라 생각하고 모든 벽을 기준으로 bfs를 돌았는데, 당연하게 시간초과가 발생했습니다. 시간을 단축시키려면 불필요한 bfs탐색을 줄여야 하기 때문에 우선 시선을 벽이 아닌 빈칸으로 잡아야합니다.
각 빈칸을 bfs탐색하여, 그룹을 나누고, 해당 그룹의 값은 인접한 그룹의 범위의 총합입니다. 섬 나누는 문제를 생각하시면 될 것 같습니다.
그룹을 나누게 되면, 벽을 부수고 이동할 때 빈칸을 만난다면 해당 빈칸이 속한 그룹의 범위값을 더해주면, 더이상 탐색을 진행하지 않아도 후에 이동할 칸의 합을 더해줄 수 있습니다. 따라서 벽들의 위치를 기준으로 상하좌우 4방향에 빈칸이 존재한다면, 해당 값을 누적합 해주고 answer배열을 완성시켜주면 해결됩니다.

📜 후기

주의할 점이, 원본 map 배열에 최종 결괏값을 갱신하면서 다시 담게되면 결과 범위가 10의 배수일 때 결괏값으로 0이 나오게 되어, 다음 탐색할 벽이 현재 수정된 인덱스를 빈칸(0)으로 인식하게 됩니다.
도저히 왜 틀리는지 이해가 안가서 20분정도 버렸네요...ㅎㅎㅎ
이걸 보신분들은 조심하십셔~.~