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

 

 

 

정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.

연결된 집의 모임인 단지를 정의하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 문제.

* 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다.

   대각선 상에 집이 있는 경우는 연결된 것이 아니다.

 

 

dfs, bfs 두 가지 방법으로 문제를 풀 수 있다.

비슷비슷한 문제들이 많은데 거의 좌표로 상하좌우의 값을 탐색하기 위해 dx, dy 배열을 만든다.

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

 

이 문제에선 입력받기 위한 변수들과 방문여부를 체크할 변수 외에

단지 번호를 카운팅 해주기 위한 변수, 각 단지에 속하는 집의 수를 카운팅 해주기 위한 변수가 필요하다.

 

 

main은 아래와 같이 통일시켰다.

public static void main(String[] args) throws IOException {
    Scanner sc = new Scanner(System.in);
    N = sc.nextInt();

    for(int i=0; i<N; ++i){
        String input = sc.next();
        for(int j=0; j<N; ++j){
            map[i][j] = input.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]){
                ++apartNum;
                bfs(i,j);
            }
        }
    }

    Arrays.sort(aparts);
    System.out.println(apartNum);

    for (int apart : aparts) {
        if (apart == 0) continue;
        System.out.println(apart);
    }
}

첫 번째 for문은 입력값을 map 배열에 저장하고, 두 번째 for문은 map을 돌며 bfs 또는 dfs를 실행시킨다.

나는 bfs로 해놓은 상태라 bfs라 되어있음

그리고 정렬하고, 출력하고..

 

 

dfs

private static void dfs(int x, int y) {
    visited[x][y] = true;
    aparts[apartNum]++;

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

        if(nx>=0 && ny>=0 && nx<N && ny<N){
            if(map[nx][ny] == 1 && !visited[nx][ny]){
                dfs(nx,ny);
            }
        }
    }
}

방문체크하고, 단지에 속한 집의 수를 ++ 해준다.

그리고 상하좌우를 돌며 집이 있다면 && 방문하지 않은 곳이라면 dfs를 호출한다.

 

 

bfs

private static void bfs(int x, int y) {
    //2차원 LinkedList를 가진 큐 선언
    Queue<int[]> que = new LinkedList<>();
    que.add(new int[]{x,y});
    visited[x][y] = true;
    aparts[apartNum]++;

    while(!que.isEmpty()){
        //x, y 값을 받아오기 위한 방법
        int curX = que.peek()[0];
        int curY = que.peek()[1];
        que.poll();

        for(int i=0; i<4; i++){
            int nx = curX + dx[i];
            int ny = curY + dy[i];

            if(nx>=0 && ny>=0 && nx<N && ny<N){
                if(map[nx][ny]==1 && !visited[nx][ny]){
                    que.add(new int[]{nx,ny});
                    visited[nx][ny] = true;
                    aparts[apartNum]++;
                }
            }
        }
    }
}

bfs니까 queue를 사용한다.

que에 현재 좌표를 추가하고, 방문체크하고, 단지에 속한 집의 수를 ++ 해준다.

그리고 que가 비워질 때 까지(=한 단지 다 돌 때 까지) 탐색한다.

 

 

import java.io.IOException;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
public class BOJ_2667 {
    static final int[] dx= {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int N;
    static int[][] map = new int[25][25]; //지도
    static boolean[][] visited = new boolean[25][25]; //방문여부
    static int apartNum = 0; //아파트 단지 번호의 수
    static final int[] aparts = new int[25*25];
 
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
 
        for(int i=0; i<N; ++i){
            String input = sc.next();
            for(int j=0; j<N; ++j){
                map[i][j] = input.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]){
                    ++apartNum;
                    bfs(i,j);
                }
            }
        }
 
        Arrays.sort(aparts);
        System.out.println(apartNum);
 
        for (int apart : aparts) {
            if (apart == 0) continue;
            System.out.println(apart);
        }
    }
 
    private static void bfs(int x, int y) {
        //2차원 LinkedList를 가진 큐 선언
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{x,y});
        visited[x][y] = true;
        aparts[apartNum]++;
 
        while(!que.isEmpty()){
            //x, y 값을 받아오기 위한 방법
            int curX = que.peek()[0];
            int curY = que.peek()[1];
            que.poll();
 
            for(int i=0; i<4; i++){
                int nx = curX + dx[i];
                int ny = curY + dy[i];
 
                if(nx>=0 && ny>=0 && nx<N && ny<N){
                    if(map[nx][ny]==1 && !visited[nx][ny]){
                        que.add(new int[]{nx,ny});
                        visited[nx][ny] = true;
                        aparts[apartNum]++;
                    }
                }
            }
        }
    }
 
    private static void dfs(int x, int y) {
        visited[x][y] = true;
        aparts[apartNum]++;
 
        for(int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if(nx>=0 && ny>=0 && nx<N && ny<N){
                if(map[nx][ny] == 1 && !visited[nx][ny]){
                    dfs(nx,ny);
                }
            }
        }
    }
}
 

 

비슷한 문제가 많이 나와서 툭 치면 코드가 나올 정도로 익숙해져야 함

근데 일단 나는 아님