오늘의 학습 키워드
</> 깊이/너비 우선 탐색(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 코드리뷰
현재 코드의 장점
- 명확한 로직: 코드의 로직이 직관적이고 명확합니다. 그리드에 직사각형을 표시한 후 DFS를 통해 빈 영역을 탐색하는 과정이 논리적으로 잘 구현되어 있습니다.
- DFS를 통한 효과적인 영역 탐색: DFS(깊이 우선 탐색)를 사용하여 영역의 크기를 계산하는 방식이 효율적입니다. 모든 가능한 방향을 탐색하고, 방문한 위치를 기록하는 방식으로 중복 탐색을 방지합니다.
- 정렬된 출력: 영역 크기를 오름차순으로 정렬하여 출력하는 부분은 문제 요구사항을 정확하게 충족시킵니다.
- 모듈화: DFS를 별도의 함수로 분리하여 코드의 재사용성과 가독성을 높였습니다.
현재 코드의 단점
- 입력 처리 성능: Scanner를 사용하여 입력을 처리하는 부분은 간단한 문제에서는 괜찮지만, 입력 데이터가 많을 경우 성능이 떨어질 수 있습니다. 특히, 입력이 매우 큰 경우 BufferedReader와 StringTokenizer를 사용하는 것이 더 효율적입니다.
- 재귀 깊이: DFS에서 재귀를 사용하는데, 그리드의 크기가 매우 큰 경우 Java의 기본 재귀 깊이 제한에 의해 StackOverflowError가 발생할 수 있습니다. 이 문제를 해결하려면 BFS(너비 우선 탐색)로 전환하거나, 재귀 깊이를 조절해야 합니다.
- 고정된 방향 탐색: 4방향(상, 하, 좌, 우) 탐색만을 고려하고 있어, 만약 문제가 대각선 탐색을 요구하거나 더 많은 방향을 고려해야 한다면 코드를 수정해야 합니다.
시간 복잡도
시간 복잡도는 O(M * N)이 됩니다. 정렬의 경우 영역의 수가 상대적으로 적기 때문에 전체 시간 복잡도에 큰 영향을 미치지 않습니다.
내일 공부할 것 :
차근히 생각하는 법 기르기, 급하게 순서 건너뛰고 생각하지 않고 최대한 자세히 짜보기
문제
모든것에 의문을 가지는 알아가는 취준생