Baekjoon 2667 단지번호 붙이기

문제 이해

Baekjoon 2667 단지번호 붙이기

2차원 평면에 아파트가 있다.

상하좌우에 아파트가 있으면 인접한 아파트라고 하고 인접한 아파트들은 묶어서 하나의 단지로 칭한다.

2차원 평면에 아파트의 위치가 표시되어 있을 때 몇 개 단지가 있는지, 각 단지는 몇 개의 아파트로 이루어져 있는지 구해야 한다.

입출력 조건 확인

맵 전체 순회하는 반복문 제외하고는 해 봐야 몇 번 안 돌고 끝나고 맵 전체 순회도 맵 최대 크기(25 × 25)도 얼마 되지 않아 여기에서 걸릴 일은 없어 보인다.

문제 풀이 내용 정리

1. 맵 그리기
   빈 땅(0)과 아파트(1)가 포함된 맵이 문자열로 주어지니 그대로 받아서 2차원 배열에 입력한다.

2. 아파트 단지 찾는 메소드 실행
   아파트 단지를 찾는다. 한 번 아파트를 찾으면 인접한 아파트를 순회해서 단지를 다 찾을 때 까지 단지 번호(count)를 유지하고 같은 인덱스에 countList를 1 증가시킨다.
   단지를 다 찾고 넘어간 후 다음 단지를 찾기 시작하면 단지 번호(count)를 1 더한다.

3. 정렬 후 출력
   미리 할당한 배열(countList)에서 단지만 포함된 인덱스만 가져와서 새로운 배열(result)에 넣은 후 정렬하고 출력한다.

Java

Baekjoon Source

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[] dX = {1, -1, 0, 0};
    static int[] dY = {0, 0, 1, -1};
    static int depth = 0;
    static int count = 0;
    static int[] countList = new int[625];

    public static void aptGroup (int x, int y) {
        if (map[x][y] == -1) {
            if (depth == 0)
                count += 1;
            
            countList[count] += 1;
            map[x][y] = count;

            for (int i = 0; i < 4; i++) {
                int nextX = x + dX[i];
                int nextY = y + dY[i];
                if (nextX < 0 | nextX >= map.length | nextY < 0 | nextY >= map.length)
                    continue;
                else {
                    depth += 1;
                    aptGroup(nextX, nextY);
                    depth -= 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int mapSize = Integer.parseInt(sc.nextLine());
        map = new int[mapSize][mapSize];
        for (int i = 0; i < mapSize; i++) {
            String tmp = sc.nextLine();
            for (int j = 0; j < mapSize; j++) {
                if (tmp.charAt(j) == '0') map[i][j] = 0;
                else map[i][j] = -1;
            }
        }

        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map.length; j++) {
                aptGroup(i, j);
            }
        }

        int[] result  = new int[count];

        for (int i = 1; i <= count; i++) {
            result[i - 1] = countList[i];
        }

        Arrays.sort(result);
        System.out.println(result.length);
        for (int value : result) {
            System.out.println(value);
        }
    }
}

코드 문제점 및 해결 방법

countList를 그냥 조건 이상으로 아주 크게 할당해서 오류를 피했는데 이런 방법 말고 더 딱 맞는 방법으로 하면 좋을 것 같다.

주 기능 메소드를 실행한 후 결과물을 출력 조건에 맞게 가공하는 코드가 생각보다 길어졌다.
더 간결하게 만들 수 있으면 좋을 것 같은데 위의 countList 때문에 벌어진 일로 보인다.