[BaekJoon] 16946 벽 부수고 이동하기 4 (Java)

1.  문제 링크

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

2.  문제

요약

• N x M의 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타냅니다.
• 한 칸에서 다른 칸으로 이동하려면 두 칸이 인접해야 하는데, 두 칸이 변을 공유할 때, 인접하다고 합니다.
• 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸입니다.
• 각각의 벽에 대해서 다음을 구하는 문제입니다.
  • 벽을 부수고 이동할 수 있는 곳으로 변경합니다.
  • 그 위치에서 이동할 수 있는 칸의 개수를 세어봅니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 N, M이 주어지고 두 번째 줄부터 N개의 줄에 M개의 숫자로 맵이 주어집니다.
• 출력: 맵의 형태로 정답을 출력합니다. 원래 빈 칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력합니다.

3.  소스코드

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

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static int[][] map, mass;
    static boolean[][] visited;
    static HashMap<Integer, Integer> massNums;
    static int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new int[N][M];

        for(int row = 0; row < N; row++) {
            String info = scanner.nextLine();

            for(int col = 0; col < M; col++)
                map[row][col] = info.charAt(col) - '0';
        }
    }

    static void solution() {
        getMassLoc();

        findReachableLocNum();

        System.out.print(sb);
    }

    static void findReachableLocNum() {
        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++) {
                if(map[row][col] == 1) {
                    HashSet<Integer> neighborMass = new HashSet<>();
                    for(int dir = 0; dir < 4; dir++) {
                        int cx = row + dx[dir], cy = col + dy[dir];

                        if(isInMap(cx, cy)) {
                            if (map[cx][cy] == 0 && mass[cx][cy] != 0)
                                neighborMass.add(mass[cx][cy]);
                        }
                    }

                    Iterator<Integer> iter = neighborMass.iterator();
                    int sum = 1;

                    while(iter.hasNext()) {
                        int neighbor = iter.next();
                        sum += massNums.get(neighbor);
                    }

                    sb.append(sum % 10);
                }

                else if(map[row][col] == 0) {
                    sb.append('0');
                }
            }
            sb.append('\n');
        }
    }

    static void getMassLoc() {
        visited = new boolean[N][M];
        mass = new int[N][M];
        massNums = new HashMap<>();

        int massNum = 0;

        for(int row = 0; row < N; row++) {
            for(int col = 0; col < M; col++) {
                if(!visited[row][col] && map[row][col] == 0) {
                    massNum++;
                    massNums.put(massNum, 0);
                    dfs(row, col, massNum);
                }
            }
        }
    }

    static void dfs(int x, int y, int massNum) {
        if(visited[x][y]) return;

        visited[x][y] = true;
        mass[x][y] = massNum;
        massNums.put(massNum, massNums.get(massNum) + 1);

        for(int dir = 0; dir < 4; dir++) {
            int cx = x + dx[dir], cy = y + dy[dir];

            if(isInMap(cx, cy)) {
                if(!visited[cx][cy] && map[cx][cy] == 0) {
                    dfs(cx ,cy, massNum);
                }
            }
        }
    }

    static boolean isInMap(int x, int y) {
        if(x >= 0 && x < N && y >= 0 && y < M) return true;
        return false;
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        String nextLine() {
            String str = "";

            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }

            return str;
        }
    }
}

4  접근

• 주어진 맵의 정보를 map이라는 2차원 배열에 저장하고 이후에 DFS를 통해 0의 집합들을 구하고 번호를 메길건데, 각 위치가 어떤 집합에 속하는지 나타낼 2차원 배열 mass와 각 집합에 속하는 위치의 개수를 나타내는 HashMap인 massNums를 생성합니다.
• 각 위치를 돌면서 DFS를 통해 집합을 구하고 각 위치가 어떤 집합에 포함되는지 mass 배열에 표시하며 각 집합에 포함되는 위치의 개수를 massNums에 저장합니다.

static void dfs(int x, int y, int massNum) {
    if(visited[x][y]) return;

    visited[x][y] = true;
    mass[x][y] = massNum;
    massNums.put(massNum, massNums.get(massNum) + 1);

    for(int dir = 0; dir < 4; dir++) {
        int cx = x + dx[dir], cy = y + dy[dir];

        if(isInMap(cx, cy)) {
            if(!visited[cx][cy] && map[cx][cy] == 0) {
                dfs(cx ,cy, massNum);
            }
        }
    }
}

• 각 위치를 돌면서 해당 위치가 벽인지 아닌지 확인하고 벽인지 아닌지에 따라 아래와 같은 행동을 취합니다.
  • 만약 벽이 아니라면
    • StringBuilder에 0을 추가하여 이후에 해당 위치는 0을 출력합니다.
  • 만약 벽이라면
    • neighborMass라는 HashSet을 생성하고 해당 위치의 인접하는 곳, 즉 상하좌우 위치를 확인하여 해당 위치가 맵 안에 존재하고 어떠한 집합에 포함된다면 해당 위치의 집합의 번호를 neighborMass에 추가합니다.
      • neighborMass에 있는 집합 번호를 돌면서 neighborMass에 있는 집합 번호들에 포함되는 위치의 개수들을 모두 더하고 해당 벽의 위치도 답에 포함되어야 하므로 모두 더한 결과에 1을 더해줍니다.
      • 더한 결과를 10으로 나눈 결과를 StringBuilder에 추가하여 해당 위치에 해당 값을 출력하도록 합니다.
  • 만약 하나의 행이 끝나는 위치라면, 즉 마지막 열이라면 위 작업을 진행한 후에 줄바꿈 문자를 추가해줍니다.

static void findReachableLocNum() {
    for(int row = 0; row < N; row++) {
        for(int col = 0; col < M; col++) {
            if(map[row][col] == 1) {
                HashSet<Integer> neighborMass = new HashSet<>();
                for(int dir = 0; dir < 4; dir++) {
                    int cx = row + dx[dir], cy = col + dy[dir];

                    if(isInMap(cx, cy)) {
                        if (map[cx][cy] == 0 && mass[cx][cy] != 0)
                            neighborMass.add(mass[cx][cy]);
                    }
                }

                Iterator<Integer> iter = neighborMass.iterator();
                int sum = 1;

                while(iter.hasNext()) {
                    int neighbor = iter.next();
                    sum += massNums.get(neighbor);
                }

                sb.append(sum % 10);
            }

            else if(map[row][col] == 0) {
                sb.append('0');
            }
        }
        sb.append('\n');
    }
}