오늘의 학습 키워드
</> 깊이/너비 우선 탐색(DFS/BFS)
공부한 내용 본인의 언어로 정리하기
import java.util.*;
public class Main{
static int M,N,K;
static int[][] square;
static boolean[][] visited;
static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
square = new int[M][N];
visited = new boolean[M][N];
for(int i = 0; i < K; i++){
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
for(int y = y1; y < y2; y++){
for(int x = x1; x < x2; x++){
square[y][x] = 1;
}
}
}
ArrayList<Integer> areas = new ArrayList<>(); //크기 탐색해서 하나씩 넣어야 돼서 사용
//빈칸 영역 탐색
for(int y = 0; y < M; y++) {
for(int x = 0; x < N; x++) {
if(square[y][x] == 0 && !visited[y][x]){
int areaSize = dfs(x,y);
areas.add(areaSize);
}
}
}
//영역 개수 출력
System.out.println(areas.size());
//배열이 아니라 ArraysList이므로 Collections 사용, 오름차순 정렬
Collections.sort(areas);
//영역 넓이 출력
for(int area : areas){
System.out.print(area+" ");
}
}
//DFS 탐색
static int dfs(int x, int y){
//현재 위치 방문 표시
visited[y][x] = true;
//영역 크기 초기화
int areaSize = 1;
//상하좌우 4방향이라서 4로 제한
for(int i = 0; i < 4; i++){
int nx = x + direction[i][0];
int ny = y + direction[i][1];
if(nx >= 0 && ny >= 0 && nx < N && ny < M && square[ny][nx] == 0 && !visited[ny][nx]){
areaSize += dfs(nx, ny);
}
}
return areaSize;
}
}
오늘의 회고
오늘 문제는 앞서 나왔던 DFS문제 유형들이 방식을 합해서 해결할 수 있는 문제처럼 보였다.
상하좌우 네 방향을 재귀 탐색하여 방문하지 않은 영역의 사이즈를 구해 반환해서 출력하면 된다고 생각했고
어제와 같이 변수들을 초기화 시켜주고 필요한 좌표들을 입력해준 후 시작했다.
static int M,N,K;
static int[][] square;
static boolean[][] visited;
static int[][] direction = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 상, 하, 좌, 우
Scanner sc = new Scanner(System.in);
M = sc.nextInt();
N = sc.nextInt();
K = sc.nextInt();
square = new int[M][N];
visited = new boolean[M][N];
for(int i = 0; i < K; i++){
int x1 = sc.nextInt();
int y1 = sc.nextInt();
int x2 = sc.nextInt();
int y2 = sc.nextInt();
for(int y = y1; y < y2; y++){
for(int x = x1; x < x2; x++){
square[y][x] = 1;
}
}
}
그리고 영역의 크기를 구해줘야 했으므로 크기들을 넣을 리스트를 하나 만들고 dfs를 이용하여 도출한 값을 리스트에 넣어주었다.
이번에 제한을 둔 사항은 사각형을 차지하는 영역의 값을 1로 두었기 때문에 사각형이 차지 하지 않은 영역이거나 방문하지 않은 영역일 경우로 두었고 해당 조건에 맞을 경우에 dfs로 탐색한 값을 받아와서 리스트에 넣어주었다.
나머지 값들을 출력하는 것은 아래와 같다.
//영역 개수 출력
System.out.println(areas.size());
//배열이 아니라 ArraysList이므로 Collections 사용, 오름차순 정렬
Collections.sort(areas);
//영역 넓이 출력
for(int area : areas){
System.out.print(area+" ");
}
가장 중요한 DFS 탐색을 만들어 준다.
static int dfs(int x, int y){
//현재 위치 방문 표시
visited[y][x] = true;
//영역 크기 초기화
int areaSize = 1;
이제 인접한 네 방향을 탐색해서 조건에 맞을경우 사이즈를 1씩 늘려줄것이다.
for(int i = 0; i < 4; i++){
int nx = x + direction[i][0];
int ny = y + direction[i][1];
if(nx >= 0 && ny >= 0 && nx < N && ny < M && square[ny][nx] == 0 && !visited[ny][nx]){
areaSize += dfs(nx, ny);
}
}
앞서 말했듯 조건은 이전 문제들에서 구한 해당 영역이 아닌 반대의 경우이기때문에 위와 같은 제한을 두었다.
마지막으로 출력을 위해 areaSize를 반환해준다
return areaSize;
AI 코드리뷰
현재 코드의 장점
현재 코드의 단점
시간 복잡도
시간 복잡도는 O(M * N)이 됩니다. 정렬의 경우 영역의 수가 상대적으로 적기 때문에 전체 시간 복잡도에 큰 영향을 미치지 않습니다.
내일 공부할 것 :
차근히 생각하는 법 기르기, 급하게 순서 건너뛰고 생각하지 않고 최대한 자세히 짜보기
문제