99클럽 코테 스터디 35일차 TIL (BFS (2))

JAVA / 실버 I. 영역 구하기

 

 

입출력 예

 

문제 해결

 

면적을 찾는 문제로 판단해서 BFS로 풀었습니다.

보통의 경우 위에서 아래로 갈수록 값이 커지는데 오늘 문제는 아래에서 위로 커집니다.
생각하기 쉽게 표를 오른쪽으로 돌렸습니다.

색이 칠해져 있는 부분은 1, 아니라면 0으로 저장하고
0인 부분만 찾고, 최초 0인 부분에서 최초 BFS를 실행합니다.
int cnt 변수의 기본값을 1로 셋팅하고(0으로 발견했으니)
상하좌우 상태에 따라 cnt++ 더해준뒤 ArrayList에 담아줬습니다.

나의 풀이

package BFS;

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

/*
백준 2583
 */
public class BFS03 {
    static int[][] map;
    static int M,N,K;
    static ArrayList<Integer> answer;
    static boolean[][] visited;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        // 예제입력 5(M) 7(N) 3(K)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 필드변수 초기화하
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        visited = new boolean[N][M];
        answer = new ArrayList<>();

        // K개 한 줄의 영역을 입력받는다
        for (int i = 0; i < K; i++) {
            String[] str = br.readLine().split(" ");

            int startX = Integer.parseInt(str[0]); // 0
            int startY = Integer.parseInt(str[1]); // 2
            int endX = Integer.parseInt(str[2]); // 4
            int endY = Integer.parseInt(str[3]); // 4

            for (int j = startX; j < endX; j++) {
                for (int k = startY; k < endY; k++) {
                    map[j][k] = 1;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if(map[i][j] == 0 && !visited[i][j]){
                    BFS(i, j);
                }
            }
        }

        Collections.sort(answer);

        sb.append(answer.size()+"\n");
        for (int num : answer){
            sb.append(num+" ");
        }

        System.out.println(sb.toString().trim());
    }

    public static void BFS(int x, int y){
        int cnt = 1;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        visited[x][y] = true;

        while (!q.isEmpty()){
            int[] arr = q.poll();
            int al = arr[0], ar = arr[1];

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

                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                // 주변 면적(상하좌우)의 값이 0이라면 +1
                if(!visited[nx][ny] && map[nx][ny] == 0){
                    cnt++;
                    q.add(new int[]{nx,ny});
                    visited[nx][ny] = true;
                }
            }
        }

        answer.add(cnt);
    }
}

 

회고

 

표를 오른쪽으로 돌려놓고 값을 설정했는데 값을 찾을때는 문제의 보기 상태로 조회를해서
2시간이나 헤맸다. 

다음 BFS문제를 풀때는 큐에 int[]는 안 이뻐보여서 객체로 넣어봐야겠다.