[백준] 단지번호 붙이기 JAVA

반응형

728x90

[백준] 단지번호 붙이기 - SILVER I 2667번

---

접근

• bfs

---

풀이

2차원 배열로 주어지는 지도를 탐색하며 붙어 지도에 총 몇 단지가 존재하는지와 단지를 이루는 집들의 수를 오름차순으로 출력하는 문제이다. 문제에서 주어지는 단지의 기준은 집이 있는, 값이 1인 좌표를 기준으로 집 한채 부터 하나의 단지로 인정하며 상하좌우로 연결되어 있는 경우 한 개의 단지로 구성된다. 상하좌우의 경우에만 단지로 인정되기 때문에 대각선에 집이 있는 경우는 다른 단지가 된다. 이전에 풀었던 문제중 상당히 비슷한 문제가 있었는데 문제 이름이 기억이 안 나서 들고 오진 못했다. 아마 포스팅 하지 않고 풀고 넘겼던 문제였던 거 같은데 어떤 플랫폼의 문제인지도 잘 기억이 나지 않는다.

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

    private static class Step {
        private final int x;
        private final int y;

        public Step(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

우선 상하좌우로 움직어야 하기에 필요한 배열과 단순한 x, y 좌표를 가지는 클래스를 만들어 주었다.

	int n = Integer.parseInt(br.readLine());
        int[][] houseMap = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            houseMap[i] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
        }

초반 입력값을 2차원 배열로 변환해 주는 과정이다.

	List<Integer> resultList = new ArrayList<>();

        boolean[][] isVisited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isVisited[i][j] && houseMap[i][j] == 1) {
                    isVisited[i][j] = true;
                    resultList.add(countHouse(houseMap, isVisited, i, j, n));
                }
            }
        }

결과를 위한 리스트를 선언했는데 이 문제 요구 출력은 첫 번째로 총단지의 수와 오름차순으로 단지 내 집의 수를 출력해야 하기 때문에 구해진 값들을 바로 출력하지 않고 리스트에 넣어주었다. 그리고 좌표를 전부 순회하며 해당 좌표를 방문하지 않았고 좌표값이 1이라면 방문체크를 한 뒤 집의 수를 세는 bfs 메서드를 실행해 준다.

    private static int countHouse(int[][] houseMap, boolean[][] isVisited, int x, int y, int n) {
        int result = 1;
        Queue<Step> que = new LinkedList<>();
        que.offer(new Step(x, y));

        while (!que.isEmpty()) {
            Step step = que.poll();

집의 수를 세는 메서드로 bfs를 수행한다. result는 집의 수를 세어 반환할 객체로 좌표값이 1인 경우 메서드를 수행하러 들어오기 때문에 현재 위치의 집을 포함하기 위해 0이 아닌 1로 초기화했다.

	    for (int d = 0; d < 4; d++) {
                int nx = step.x + dx[d];
                int ny = step.y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || houseMap[nx][ny] == 0) {
                    continue;
                }

                if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Step(nx, ny));
                isVisited[nx][ny] = true;
                result++;
            }

상하좌우로 이동하며 큐에 다음 좌표를 넣어주는 과정이다. 지도의 범위 밖이거나 다음 좌표 값이 0이라면 추가하지 않고 넘어가고 다음 좌표를 방문한 경우에도 넘어가게 된다. 그렇게 다음 좌표값을 큐에 추가하고 방문 체크를 한 경우 다음 좌표에 집이 있기 때문에 집의 수인 result 값을 증가시켜 준다.

	bw.write(resultList.size()+"\n");
        Collections.sort(resultList);

        for (Integer i : resultList) {
            bw.write(i+"\n");
        }

순회가 종료되고 결과들이 추가된 리스트의 크기를 반환해 총 단지 수를 출력하고 오름차순으로 정렬하여 집들의 개수를 출력한다.

---

전체 코드

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

public class Main {
    private static final int[] dx = {0, 0, -1, 1};
    private static final int[] dy = {1, -1, 0, 0};

    private static class Step {
        private final int x;
        private final int y;

        public Step(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] houseMap = new int[n][n];

        for (int i = 0; i < n; i++) {
            String[] line = br.readLine().split("");
            houseMap[i] = Arrays.stream(line).mapToInt(Integer::parseInt).toArray();
        }

        List<Integer> resultList = new ArrayList<>();

        boolean[][] isVisited = new boolean[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (!isVisited[i][j] && houseMap[i][j] == 1) {
                    isVisited[i][j] = true;
                    resultList.add(countHouse(houseMap, isVisited, i, j, n));
                }
            }
        }

        bw.write(resultList.size()+"\n");
        Collections.sort(resultList);

        for (Integer i : resultList) {
            bw.write(i+"\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static int countHouse(int[][] houseMap, boolean[][] isVisited, int x, int y, int n) {
        int result = 1;
        Queue<Step> que = new LinkedList<>();
        que.offer(new Step(x, y));

        while (!que.isEmpty()) {
            Step step = que.poll();

            for (int d = 0; d < 4; d++) {
                int nx = step.x + dx[d];
                int ny = step.y + dy[d];

                if (nx < 0 || nx >= n || ny < 0 || ny >= n || houseMap[nx][ny] == 0) {
                    continue;
                }

                if (isVisited[nx][ny]) {
                    continue;
                }

                que.offer(new Step(nx, ny));
                isVisited[nx][ny] = true;
                result++;
            }
        }

        return result;
    }
}