[Java] 2583번 : 영역 구하기

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

 

저번에 풀었던 문제였는데, 그때 어떻게 풀었더라,,,쨋든 c++로 풀려있더라,,,ㅎ

Java로 다시 풀었다,,,! 음 풀면서 느낀건데, 이전보다는 그나마 실력이 늘긴 한듯 싶었다.

나는 dfs로 풀이했다. 보통 이런 컴포넌트 구하는 거는 dfs 로 접근하는것같다.

public static int dfs(int y, int x) {
        int cnt=1;
        visited[y][x] = true;
        for(int i=0;i<4;i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
            if(!visited[ny][nx] && arr[ny][nx]==0) {
                cnt+=dfs(ny,nx);
            }
        }
        return cnt;
    }

 

int cnt를 1로 초기화해두고, 재귀가 돌때마다 ++ 해주는 방식으로 풀었다.

그리고 시작점과 끝점을 입력받아 미리 1로 바꿔두었당. 0 부분만 탐색하도록! 

for(int i=0;i<k;i++) {
            st= new StringTokenizer(br.readLine());
            int sX = Integer.parseInt(st.nextToken());
            int sY = Integer.parseInt(st.nextToken());
            int eX = Integer.parseInt(st.nextToken());
            int eY = Integer.parseInt(st.nextToken());

            for(int j=sY;j<eY;j++) {
                for(int l=sX;l<eX;l++) {
                    arr[l][j]=1;
                }
            }
        }

 

ret은 컴포넌트 갯수 즉, 큰 덩어리의 개수이고, list에 들어가는 것들은 각 컴포넌트의 영역 개수이다. 말이 어렵나??

졸려서 그런지 내가 무슨 말을 하고있나 싶다,,,

컴포넌트는 큰 덩어리, 영역은 한칸 이라고 보면 되겠다! 

int ret = 0;
List<Integer> list = new ArrayList<>();
for(int i=0;i<n;i++) {
    for(int j=0;j<m;j++) {
        if(!visited[i][j] && arr[i][j]==0) {
            list.add(dfs(i,j));
            ret++;
        }
    };
}

Collections.sort(list);

System.out.println(ret);
for(int i=0;i<list.size();i++) {
    System.out.print(list.get(i)+ " ");
}

 

[전체코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int m, n, k;
    static int arr[][];
    static boolean visited[][];
    static int dy[] = {-1, 1, 0,0};
    static int dx[] = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken()); //5
        n = Integer.parseInt(st.nextToken()); // 7
        k = Integer.parseInt(st.nextToken()); // 3

        arr = new int[n][m];
        visited = new boolean[n][m];

        for(int i=0;i<k;i++) {
            st= new StringTokenizer(br.readLine());
            int sX = Integer.parseInt(st.nextToken());
            int sY = Integer.parseInt(st.nextToken());
            int eX = Integer.parseInt(st.nextToken());
            int eY = Integer.parseInt(st.nextToken());

            for(int j=sY;j<eY;j++) {
                for(int l=sX;l<eX;l++) {
                    arr[l][j]=1;
                }
            }
        }

        int ret = 0;
        List<Integer> list = new ArrayList<>();
        for(int i=0;i<n;i++) {
            for(int j=0;j<m;j++) {
                if(!visited[i][j] && arr[i][j]==0) {
                    list.add(dfs(i,j));
                    ret++;
                }
            };
        }

        Collections.sort(list);

        System.out.println(ret);
        for(int i=0;i<list.size();i++) {
            System.out.print(list.get(i)+ " ");
        }

    }

    public static int dfs(int y, int x) {
        int cnt=1;
        visited[y][x] = true;
        for(int i=0;i<4;i++) {
            int ny = dy[i] + y;
            int nx = dx[i] + x;
            if(ny<0 || nx<0 || ny>=n || nx>=m) continue;
            if(!visited[ny][nx] && arr[ny][nx]==0) {
                cnt+=dfs(ny,nx);
            }
        }
        return cnt;
    }


}