[Algorithm] 백준_2667 단지번호 붙이기

lnnae·2020년 4월 9일

Algorithm

목록 보기

4/40

문제

풀이

첫 번째 줄에 입력받은 수 n으로 map (2차원 배열)을 생성한다.

이 다음부터 한 줄을 string으로 입력받았고, 문자열에서 한 문자씩 읽어들이면서 배열에 넣어줌 → chatAt() 메소드 사용했고, -'0' 처리해서 문자→숫자로 변경
현재 map과 똑같은 크기의 visited 불린 배열 생성해서 방문 여부를 관리한다.
다시 이중 for문을 돌면서, 값이 1이고(집이 있고) 방문하지 않았다면 bfs 탐색을 한다.

bfs로 한 이유는.. 수를 세는거니까 최소 경로로 하면 더 좋을 것 같다는 뇌피셜하에..
bfs 함수를 호출할 때 마다 total 변수의 값을 1씩 증가
함수 내에서는 Queue를 사용해서 다음에 방문할 집을 관리한다.

Queue에 좌표를 넣을 때는 String 형식으로 ','를 구분자로 사용해 넣어줬고, 좌표값으로 사용할때는 split()함수로 구분해서 사용했다.
인접한 집을 계산할 때는 for문에서 4번씩 반복하며 상,하,좌,우의 케이스를 따져서 방문한 적이 없는 집이고, 값이 1이면 방문한다.

+또 좌표의 값이 0< x<n인지 확인해야한다.
BFS 함수 내에서 Queue에 들어간 집 수를 배열에 넣어주고 정렬해서 출력

sort()메소드 사용했다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_2667 {

    static final int[] dx = {0, 0, -1, 1};
    static final int[] dy = {1, -1, 0, 0};
    static boolean[][] visited;
    static int[][] map;
    static int n; //지도 행 수
    static int total;  // 전체 단지 수
    static ArrayList<Integer> house = new ArrayList<>(); //단지 별 가구 수

    public static void bfs(int i, int j) {
        total++;
        int count=0;

        Queue<String> q = new LinkedList<>();
        q.add(i + "," + j);
        visited[i][j] = true;

        while(!q.isEmpty()) {
            count++;
            String[] str = q.poll().split(",");
            for (int z=0; z<4; z++) {
                int row = Integer.parseInt(str[0]);
                int col = Integer.parseInt(str[1]);
                row += dx[z];
                col += dy[z];

                if(row < 0 || row > n || col < 0 || col > n) {
                    continue;
                }

                if (!visited[row][col] && map[row][col] == 1) {
                    q.add(row + "," + col);
                    visited[row][col] = true;
                }
            }
        }
        house.add(count);
    }

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

        n = Integer.parseInt(br.readLine());
        visited = new boolean[n+1][n+1];

        map = new int[n+1][n+1];

        /* 맵 생성 */
        for (int i = 1; i <= n; i++) {
            input = br.readLine();
            for (int j = 1; j <= n; j++) {
                map[i][j] = input.charAt(j - 1) - '0';
            }
        }

        for (int i = 1; i <= n; i++) {
            for(int j=1; j<=n; j++) {
                //값이 1이고, 방문하지 않은 집
                if (map[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j);
                }
            }
        }

        System.out.println(total);

        house.sort(null); //오름차순 정렬

        for(int i: house) {
            System.out.println(i);
        }
    }
}