백준 2583번: 영역 구하기

왠지 DFS와 BFS 둘다 가능할 것 같아여 유형 익힐겸 둘다 풀어보았다.

 

문제 푸는시간보다 문제를 이해하는데 더 오랜시간이 걸렸다..

5x7 (가로,행x세로,열)의 배열이 있다.

우선 문제에서 0.0의 위치는 일반적인 배열의 위치인 왼쪽 위가 아닌 왼쪽 아래이다.

왼쪽아래에서 부터 열을 고정하고 위로 올라갈 수록 x좌표가 아닌 y좌표 값이 올라가는 형태이다.

나는 이게 넘 헷갈려서 값을 뒤집어서 받아줬다. x들어올 곳에 y를 넣은 상황.

 

꼭짓점을 제공하고 그걸통해 직사각형을 구해야한다.

제공되는 꼭짓점 값이 곧 해당 배열의 칸이아니기 때문에 사각형을 그리려면

오른쪽 아래x,y에 -1을 해주어야 한다.

 

ex) 왼쪽 위 꼭짓점 : {0,2} , 오른쪽 아래 꼭짓점 : {4,4} 인 경우

꼭짓점을 배열 칸 기준으로 생각하게 되면 왼쪽그림과 같이 size over가 난다. 

그래서 오른쪽 부분을 -1 해주는 것..

 

 

배열꼬아서 내면 너무 헷갈려서 더 머리가 혼란스러워진다...........

 

(1) DFS로 푼 코드

0이고 방문하지 않은 것들을 모두 싹 돌면서 0이면 무조건 방문true처리 & cnt++ 한다.

package algorithm;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class Fun2583 {

	public static int N,M,K,ans=0,cnt=0;
	public static int[][] map;
	public static boolean[][] visit;
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {1,0,-1,0};
	public static ArrayList<Integer> ansList;
	public static void main(String[] args) throws FileNotFoundException {
		
		System.setIn(new FileInputStream("Fun2583.txt"));
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt(); //가로 행
		N = sc.nextInt(); //세로 열
		K = sc.nextInt();
		
		map = new int[M][N];
		visit = new boolean[M][N];
		ansList = new ArrayList<Integer>(); 

		for (int k = 0; k < K; k++) {
			
			//꼭짓점 != 칸
			//{0,2} ,{4,4} 의 꼭지점이 주어졌을 때, 사각형을 그리려면  {0.2}~{3.3} 이 범위를 따라야함 오른쪽 아래 x,y에 각각 -1 해줄것.
			//제공되는 문제는 0.0부터 오른쪽으로 갈수록 x값이 증가하는 배열의 형태를 띄고있다..(ex. {0.0} {1.0} {2.0} {3.0} ... {7.0}) 나는 그게 헷갈려서
			//0.0부터 오른쪽으로 갈수록 y값이 증가하는 형태로 만들기 위해 x,y좌표 위치를 바꿔서 받아줬다. (y부터 먼저 받음)
			int leftY = sc.nextInt(); //직사각형의 왼쪽 위 y
			int leftX = sc.nextInt(); //직사각형의 왼쪽 위 x
			int rightY = sc.nextInt(); //직사각형의 오른쪽 아래 y
			int rightX = sc.nextInt(); //직사각형의 오른쪽 아래 x
			
			
			for (int i = 0 ; i <= rightX-leftX-1; i++) {
				for (int j = 0; j <= rightY-leftY-1; j++) {
					map[leftX+i][leftY+j] = 1; //직사각형 범위 표시
				}
			}	
		}
		
//		for (int i = 0; i < map.length; i++) {
//			for (int j = 0; j < map[0].length; j++) {
//				System.out.print(map[i][j]);
//			}
//			System.out.println();
//		}
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j]==0 && !visit[i][j]) {
					cnt=0;
					dfs(i,j);
					ansList.add(cnt);
				}
			}
		}
		
		Collections.sort(ansList);
		System.out.println(ansList.size());
		for(Integer i :ansList) {
			System.out.print(i+" ");
		}
		System.out.println();
		
	}
	public static void dfs(int row, int col) {
		
		cnt++; //0을 찾았다면 무조건 카운팅
		visit[row][col]=true;
		//방향 탐색
		for (int i = 0; i < dx.length; i++) {
			int nx = row + dx[i];
			int ny = col + dy[i];
			
			//종료조건
			//범위 벗어나냐?
			if(nx >= M || ny >= N || nx < 0 || ny < 0)
				continue;
			//직사각형 범위에 포함되냐?
			if(map[nx][ny]==1) {
				continue;
			}
			//이미 들렸던 곳이냐?
			if(visit[nx][ny])
				continue;
			
			dfs(nx,ny);
		}
	}

}

 

(2) BFS로 푼 코드

BFS가 맞는지는..모르겠지만 무튼 재귀함수아니고... 큐+while문 쓴것

import java.util.*;

public class Main {

	public static int N,M,K,ans=0,cnt=0;
	public static int[][] map;
	public static boolean[][] visit;
	public static int[] dx = {0,1,0,-1};
	public static int[] dy = {1,0,-1,0};
	public static ArrayList<Integer> ansList;
	public static Queue<Integer[]> q;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		M = sc.nextInt(); //가로 행
		N = sc.nextInt(); //세로 열
		K = sc.nextInt();
		
		map = new int[M][N];
		visit = new boolean[M][N];
		ansList = new ArrayList<Integer>(); 
		q = new LinkedList<Integer[]>();
		
		for (int k = 0; k < K; k++) {
			
			//꼭짓점 != 칸
			//{0,2} ,{4,4} 의 꼭지점이 주어졌을 때, 사각형을 그리려면  {0.2}~{3.3} 이 범위를 따라야함 오른쪽 아래 x,y에 각각 -1 해줄것.
			//제공되는 문제는 0.0부터 오른쪽으로 갈수록 x값이 증가하는 배열의 형태를 띄고있다..(ex. {0.0} {1.0} {2.0} {3.0} ... {7.0}) 나는 그게 헷갈려서
			//0.0부터 오른쪽으로 갈수록 y값이 증가하는 형태로 만들기 위해 x,y좌표 위치를 바꿔서 받아줬다. (y부터 먼저 받음)
			int leftY = sc.nextInt(); //직사각형의 왼쪽 위 y
			int leftX = sc.nextInt(); //직사각형의 왼쪽 위 x
			int rightY = sc.nextInt(); //직사각형의 오른쪽 아래 y
			int rightX = sc.nextInt(); //직사각형의 오른쪽 아래 x
			
			
			for (int i = 0 ; i <= rightX-leftX-1; i++) {
				for (int j = 0; j <= rightY-leftY-1; j++) {
					map[leftX+i][leftY+j] = 1; //직사각형 범위 표시
				}
			}	
		}
		
		
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if(map[i][j]==0 && !visit[i][j]) {

					visit[i][j]=true;
					cnt=1; //최초로 찾은 0인 거 카운트
					q.add(new Integer[]{i,j}); // row,col를 넣은 Integer[]
					bfs();
				}
			}
		}
		
		Collections.sort(ansList);
		System.out.println(ansList.size());
		for(Integer i :ansList) {
			System.out.print(i+" ");
		}
		System.out.println();
		
	}
	public static void bfs() {
		
		while(!q.isEmpty()) { //큐가 빌 때까지
			Integer[] pos = q.poll();
			
			for (int i = 0; i < dx.length; i++) {
				int nx = pos[0] + dx[i];
				int ny = pos[1] + dy[i];
				
				//범위 벗어나냐?
				if(nx >= M || ny >= N || nx < 0 || ny < 0)
					continue;
				//직사각형 범위에 포함되냐?
				if(map[nx][ny]==1) {
					continue;
				}
				//이미 들렸던 곳이냐?
				if(visit[nx][ny])
					continue;
				
				visit[nx][ny]=true;
				cnt++;
				q.add(new Integer[]{nx,ny});
				
			}
		}
		ansList.add(cnt);

	}
	

}

 

 

 

놀랍게도 dfs로 쓴게 메모리랑 시간이 더 낫다.. 하하하.?