[BaekJoon] 백준 2583번 _ 영역 구하기 for JAVA _ DFS 알고리즘

 

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

2583번: 영역 구하기

 

 

 

문제

 

 

 

---

 

DFS로 풀었음

 

 

탐색 문제는 다 비슷비슷 한 것 같다. 보자마자 DFS 아니면 BFS를 써야겠다 싶은....

 

 

쉬운 문제만 푸는건가? 뭐 암튼..

 

 

 

여기서 주의할점은.... 문제에 그려진 배열로 생각하면 안된다는거랑... 입력에 주어지는 숫자대로 배열을 만들면 안된다는...것이다.

 

 

우선 문제에

 

 

 

그림이 이렇게 그려져있는데 우리는 배열을 만들 때 (0,0)이 왼쪽 위에 가게 하므로

 

 

 

 

 

이렇게 봐야함. 그래서 주어진 M, N도 가로가 N이고 세로가 M이다.

 

 

그리고!! 예시에서 0 2 4 4 일케 그려졌을 때

 

 

 

 

 

저기 색칠한 부분인데 보다시피 4 4 가 아니라 (3,3)까지만 칠해진다.

 

 

 

그래서 입력받은 두 좌표에서 뒷 좌표는 각각 1씩 뺀 배열까지 칠해지게 된다.

 

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;


public class Baek2583 { // DFS
	public static ArrayList<Integer> count = new ArrayList<Integer>();
	public static int map[][];
	public static int M, N, K, Allcount = 0, index = 0;
	public static int dx[] = {1, -1, 0, 0};
	public static int dy[] = {0, 0, 1, -1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		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];
		
		int in[] = new int[4];
		for(int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			in[0] = Integer.parseInt(st.nextToken());
			in[1] = Integer.parseInt(st.nextToken());
			in[2] = Integer.parseInt(st.nextToken());
			in[3] = Integer.parseInt(st.nextToken());
			
			for(int x = in[0]; x < in[2]; x++)
				for(int y = in[1]; y < in[3]; y++)
					map[x][y] = 1;
		}
		
		
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				if(map[i][j] == 0) {
					index++;
					dfs(i, j);
					count.add(Allcount, index);
					Allcount++;
					index = 0;
				}
		
		Collections.sort(count);
		System.out.println(Allcount + " ");
		for(int i = 0; i < count.size(); i++)
			System.out.print(count.get(i) + " ");
		
	}
	
	public static void dfs(int x, int y) {
		map[x][y] = 1;
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx <= -1 || nx >= N || ny <= -1 || ny >= M) continue;
			if(map[nx][ny] == 0) {
				dfs(nx, ny);
				index++;
			}
		}
	}

}

 

 

 

나는 칠한부분을 1 안칠한 부분을 0으로 map[][]에 넣었다.

 

 

 

 

 

 

성능

 

 

 

 

 

여러 부분에서 보면 그리 좋은 코드는 아닌 것 같다.

 

 

특히 안칠한부분 개수 세는 부분이 너무 비효율적인 것 같아서 다른사람 코드를 살펴보겠다.

 

 

 

 

---

 

아 다들 비슷하게 했네요~

 

 

 

 

https://www.acmicpc.net/source/35794476

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int[][] board;
    static int M,N,K;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine().trim());
        ArrayList<Integer> answer = new ArrayList<>();
        M = Integer.parseInt(st.nextToken());//세로
        N = Integer.parseInt(st.nextToken());//가로
        K = Integer.parseInt(st.nextToken());//색종이수
        board = new int[M][N];
        v = new boolean[M][N];
        for(int i=0; i < K; i++){
            st = new StringTokenizer(br.readLine().trim());
            int sC = Integer.parseInt(st.nextToken());
            int sR = Integer.parseInt(st.nextToken());
            int dC = Integer.parseInt(st.nextToken());
            int dR = Integer.parseInt(st.nextToken());
            for(int c = sC; c < dC ; c++){
                for(int r = sR; r < dR; r++){
                    board[r][c] = 1;
                }
            }
        }

        for(int r=0;r<M;r++){
            for(int c=0;c<N;c++){
                if(board[r][c] == 0 && !v[r][c]) answer.add(DFS(r,c));
            }
        }

        Collections.sort(answer);
        System.out.println(answer.size());
        for(Integer a : answer) System.out.print(a + " ");
    }
    static boolean[][] v;
    static int[] dr = {0,-1,0,1};
    static int[] dc = {-1,0,1,0};
    static int DFS(int r, int c){
        int cnt = 1;
        v[r][c] = true;

        for(int d =0; d < dr.length; d++){
            int nr = r + dr[d];
            int nc = c + dc[d];
            if(nr < 0 || nc < 0 || nr >= M || nc >= N || v[nr][nc] || board[nr][nc]!=0) continue;
            cnt += DFS(nr,nc);
        }
        return cnt;
    }
}

 

 

 

이게 그나마 ArrayList 쓰고 cnt += DFS() 이런식으로 해서 나름 효율적으로 짜여진 것 같다!