[Java] 백준 2667 : 단지번호붙이기

[Java] 백준 2667 : 단지번호붙이기

---

2667번: 단지번호붙이기

 

입력해야하는 값이 아래와 같이 주어진다.

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

첫째줄은 지도의 크기 N이며, 그 다음 N줄에는 N개의 자료가 입력된다.

위의 정보를 토대로 NxN 크기의 map을 먼저 만들어야 한다.

 

각 행마다 하나의 문자열을 받는다고 가정하면,

0번 행에는 '0110100'이라는 문자열을 분리하여 각각의 행에 정수로 치환한 값을 할당해야 한다.

 

StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String temp = st.nextToken(); // 각 행마다 하나의 문자열 입력 받음
            for (int j = 0; j < N; j++) {
                map[i][j] = temp.charAt(j) - '0'; // 문자를 정수로 치환하여 각 열에 할당
            }
        }

 

map이 완성되었으니 이중 반복문으로 탐색을 시작한다.

만약 방문되지 않았는데 값이 1인(집이 위치한) 좌표가 나타나면 새로운 단지가 나타난 것이므로

단지의 총 개수에 1을 더하고 dfs 또는 bfs를 통해 단지 내 집의 개수를 구하는 메서드를 구현한다.

 

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        if (map[i][j] == 1 && !visited[i][j]) {
            // 집이 있는데 방문이 안된 곳이 있으면 단지수를 추가하고 해당 단지의 집이 몇개 있는지 bfs로 계산하기
            danjiNum++;
            countingHouseBFS(i, j);
        }
    }
}

 

bfs로 구현할 경우, 큐를 활용하여 방문처리를 할 수 있다.

bfs에 주어지는 매개변수는 탐색자의 x, y 좌표 값이므로 큐에 두 개의 값을 넣었다 뺐다 할 수 있도록 객체를 선언한다.

static class Point { // 큐에서 x, y 좌표 뽑아내기용 객체
    int x;
    int y;
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

 

그리고 탐색자가 이동할 수 있는 모든 경우의 수를 반복문을 통해 구현하기 위해 x, y값에 대한 후보군을 배열로 선언한다.

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

현재의 위치에 위의 값을 반복문을 통해 더해주면 탐색자가 이동할 좌표를 지정할 수 있다.

 

bfs가 시작되면, 먼저 최초의 좌표를 큐에다 집어 넣고 방문처리를 한다.

또한, 해당 단지의 집 개수를 1 증가시킨다.

public static void countingHouseBFS(int i, int j) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(i, j)); // 큐에 새로운 단지의 시작 주소를 좌표값으로 집어 넣음
        visited[i][j] = true;
        danji[danjiNum]++; // 해당 단지 번호의 집 개수를 하나 올림

 

큐에 값이 하나도 남지 않을 때까지 반복문을 돌린다.

먼저 큐에서 값을 하나 뽑고, 탐색자의 현 위치에서 상하좌우를 돌아다니면서 탐색하도록 한다.

이때, 탐색자가 map의 위치를 벗어나지 않도록 한다.

 

탐색자의 새로운 위치에 1이 있고(집이 있고) 방문처리가 되지 않았다면 현재 위치한 단지와 같은 단지 내의 또다른 집으로 인식할 수 있다.

따라서 큐에 해당 좌표를 넣고 방문처리를 하며 해당 단지의 집 개수를 1 증가시킨다.

while(!q.isEmpty()) {
            // 큐에서 값 하나 뽑기
            Point temp = q.poll();
            // 상하좌우를 돌아다니면서 탐색하기
            for (int k = 0; k < 4; k++) {
                int x = temp.x + dx[k];
                int y = temp.y + dy[k];
                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (map[x][y] == 1 && !visited[x][y]) {
                        // 움직인 위치가 map 범위 내에 있고, 집이 있고, 방문처리가 되지 않았을 경우
                        // 큐에 좌표를 넣고 방문처리 하고 해당 단지번호의 집 개수를 하나 올림
                        q.add(new Point(x, y));
                        visited[x][y] = true;
                        danji[danjiNum]++;
                    }
                }
            }
        }

 

danzi는 각 단지별로 집의 총 개수가 포함되어 있는 배열이다.

NxN 크기의 map의 경우, 단지는 최대 N*N개가 있을 수 있다.

 

각 단지내 집의 수를 오름차순으로 정렬하여 출력하되, 단지로 지정되지 않은 인덱스의 값은 0이기 때문에 그 점을 고려하여 출력하였다.

Arrays.sort(danji);
System.out.println(danjiNum);

for (int i = 1; i < danji.length; i++) {
    if (danji[i] != 0) System.out.println(danji[i]);
}

 

 

전체 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Point { // 큐에서 x, y 좌표 뽑아내기용 객체
        int x;
        int y;
        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static int N, danjiNum = 0;
    static int dx[] = { -1, 1, 0, 0 };
    static int dy[] = { 0, 0, -1, 1 };
    static int [] danji;
    static int [][] map;
    static boolean [][] visited;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        visited = new boolean[N][N];
        danji = new int[N * N]; // NXN 크기 맵에서 단지 최대 개수는 N*N


        StringTokenizer st;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            String temp = st.nextToken(); // 각 행마다 하나의 문자열 입력 받음
            for (int j = 0; j < N; j++) {
                map[i][j] = temp.charAt(j) - '0'; // 문자를 정수로 치환하여 각 열에 할당
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    // 집이 있는데 방문이 안된 곳이 있으면 단지수를 추가하고 해당 단지의 집이 몇개 있는지 bfs로 계산하기
                    danjiNum++;
                    countingHouseBFS(i, j);
                }
            }
        }

        Arrays.sort(danji);
        System.out.println(danjiNum);

        for (int i = 1; i < danji.length; i++) {
            if (danji[i] != 0) System.out.println(danji[i]);
        }


    }
    public static void countingHouseBFS(int i, int j) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(i, j)); // 큐에 새로운 단지의 시작 주소를 좌표값으로 집어 넣음
        visited[i][j] = true;
        danji[danjiNum]++; // 해당 단지 번호의 집 개수를 하나 올림

        while(!q.isEmpty()) {
            // 큐에서 값 하나 뽑기
            Point temp = q.poll();
            // 상하좌우를 돌아다니면서 탐색하기
            for (int k = 0; k < 4; k++) {
                int x = temp.x + dx[k];
                int y = temp.y + dy[k];
                if (x >= 0 && y >= 0 && x < N && y < N) {
                    if (map[x][y] == 1 && !visited[x][y]) {
                        // 움직인 위치가 map 범위 내에 있고, 집이 있고, 방문처리가 되지 않았을 경우
                        // 큐에 좌표를 넣고 방문처리 하고 해당 단지번호의 집 개수를 하나 올림
                        q.add(new Point(x, y));
                        visited[x][y] = true;
                        danji[danjiNum]++;
                    }
                }
            }
        }
    }
}