오늘의 학습 키워드
</> 깊이/너비 우선 탐색(DFS/BFS)
공부한 내용 본인의 언어로 정리하기
import java.io.*;
import java.util.*;
public class Main {
// 방향을 나타내는 이차원 배열
private static final int[][] DIRECTIONS = {
{-1, 0}, // 상
{1, 0}, // 하
{0, -1}, // 좌
{0, 1}, // 우
{-1, -1}, // 좌상
{-1, 1}, // 우상
{1, -1}, // 좌하
{1, 1} // 우하
};
//DFS 탐색
//주어진 셀에서 시작해서 값이 0이 아닌 셀들을 탐색
private static void bfs(int[][] map, int x, int y){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{x, y});
map[x][y] = 0; // 방문 처리: 나쁜 풀을 0으로 설정
while(!queue.isEmpty()){
int[] current = queue.poll();
int cx = current[0];
int cy = current[1];
for(int[] dir : DIRECTIONS){
int nx = cx + dir[0];
int ny = cy + dir[1];
//유효성 검사: 범위 체크 및 값 확인
if(nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && map[nx][ny] != 0){
//유효한 셀을 큐에 추가
queue.add(new int[]{nx,ny});
//방문 처리
map[nx][ny] = 0;
}
}
}
}
//섬의 개수 세기
private static int countIslands(int[][] map){
int R = map.length;
int C = map[0].length;
int count = 0;
//모든 셀을 순회하며 0이 아닌 값을 찾음
for(int i = 0; i < R; i++){
for(int j = 0; j < C; j++){
if(map[i][j] != 0){
bfs(map, i ,j);
count++;
}
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 첫 번째 줄에서 행과 열의 크기를 읽음
String[] firstLine = br.readLine().split(" ");
int R = Integer.parseInt(firstLine[0]);
int C = Integer.parseInt(firstLine[1]);
int[][]map = new int[R][C];
for (int i = 0; i < R; i++) {
// 각 행의 데이터를 읽어 배열에 저장
String[] row = br.readLine().split(" ");
for (int j = 0; j < C; j++) {
map[i][j] = Integer.parseInt(row[j]);
}
}
br.close();
int result = countIslands(map); // 섬의 개수를 계산
System.out.println(result);
}
}오늘의 회고
문제를 보니 실버2 문제였다...이게 과연 비기너의 수준에 맞는걸까...주변 사람들에게 물어보니 직접 푼 사람이 없었던 것 처럼 보인다.
오늘도 문제는 겨우 10분만에 이해했지만 어떻게 진행을 해야할지 감도 안잡혀서 GPT의 도움을 받아 문제 풀이의 과정을 이해하려고 노력하는 것을 목표로 진행했다.
하지만 전 방향을 순회해서 확인하는것과 큐값을 순차적으로 뽑아서 체크를 하고 방문처리를 한다는것 이외에는 너무 어려워서 이해가 힘들다...
실버2 문제 풀려면 아직 정말 많은 문제를 경험해야 할 것 같다..
AI 코드리뷰
현재 코드의 장점
- 명확한 구조: BFS(너비 우선 탐색)를 사용하여 섬을 탐색하고, BFS의 큐 기반 접근이 명확하게 구현되어 있습니다.
- 유효성 검사: 범위와 값의 유효성 검사를 통해 잘못된 인덱스 접근을 방지합니다.
- 방문 처리: 방문한 셀을 0으로 설정하여 중복 방문을 방지하고, DFS와 달리 BFS는 큐를 사용해 반복문으로 간결하게 구현되어 있습니다.
현재 코드의 단점
- 메모리 사용: map 배열을 직접 수정하여 방문 여부를 체크하는 방식은 원본 데이터를 변경하므로, 원본 데이터가 필요한 경우에 적합하지 않습니다.
- 오버헤드: BFS를 구현할 때 큐를 사용하는데, 이는 메모리와 연산 측면에서 DFS보다 약간 더 오버헤드가 있을 수 있습니다.
- 해결 방법: DFS(깊이 우선 탐색)도 같은 문제를 해결할 수 있으며, 스택을 사용하면 메모리 사용을 줄일 수 있습니다.
시간 복잡도
- 시간복잡도: O(R * C)
각 셀을 한 번씩 방문하며, 모든 이웃 셀을 체크하므로 O(R * C)입니다. - 공간복잡도: O(R * C)
큐에 모든 셀을 추가할 수 있으며, 최대 큐의 크기는 O(R * C)입니다.
개선된 코드 리뷰
import java.io.*;
import java.util.*;
public class Main {
// 방향을 나타내는 이차원 배열
private static final int[][] DIRECTIONS = {
{-1, 0}, // 상
{1, 0}, // 하
{0, -1}, // 좌
{0, 1}, // 우
{-1, -1}, // 좌상
{-1, 1}, // 우상
{1, -1}, // 좌하
{1, 1} // 우하
};
// DFS 탐색
private static void dfs(int[][] map, boolean[][] visited, int x, int y) {
Stack<int[]> stack = new Stack<>();
stack.push(new int[]{x, y});
visited[x][y] = true;
while (!stack.isEmpty()) {
int[] current = stack.pop();
int cx = current[0];
int cy = current[1];
for (int[] dir : DIRECTIONS) {
int nx = cx + dir[0];
int ny = cy + dir[1];
if (nx >= 0 && nx < map.length && ny >= 0 && ny < map[0].length && map[nx][ny] != 0 && !visited[nx][ny]) {
stack.push(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
// 섬의 개수 세기
private static int countIslands(int[][] map) {
int R = map.length;
int C = map[0].length;
int count = 0;
boolean[][] visited = new boolean[R][C];
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
if (map[i][j] != 0 && !visited[i][j]) {
dfs(map, visited, i, j);
count++;
}
}
}
return count;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] firstLine = br.readLine().split(" ");
int R = Integer.parseInt(firstLine[0]);
int C = Integer.parseInt(firstLine[1]);
int[][] map = new int[R][C];
for (int i = 0; i < R; i++) {
String[] row = br.readLine().split(" ");
for (int j = 0; j < C; j++) {
map[i][j] = Integer.parseInt(row[j]);
}
}
br.close();
int result = countIslands(map);
System.out.println(result);
}
}
개선된 버전의 장점
- 원본 데이터 보존: map 배열을 변경하지 않고, visited 배열을 사용하여 방문 여부를 관리하므로 원본 데이터를 유지할 수 있습니다.
- DFS 사용: 스택을 사용한 DFS는 큐 기반 BFS보다 메모리 사용 측면에서 조금 더 유리할 수 있습니다.
- 명확한 방문 관리: visited 배열을 통해 방문 여부를 명확하게 관리합니다.
개선된 버전의 단점
- 추가 메모리 사용: 별도의 visited 배열을 사용하므로 메모리 사용이 약간 증가합니다.
- 스택 오버헤드: 스택을 사용하여 DFS를 구현하는데, 스택의 크기가 큰 경우 성능이 영향을 받을 수 있습니다.
시간 복잡도
- 시간복잡도: O(R * C)
모든 셀을 한 번씩 방문하므로 시간복잡도는 변하지 않습니다. - 공간복잡도: O(R * C)
visited 배열과 스택에 대한 공간을 추가로 사용합니다.
내일 공부할 것 :
DFS와 BFS에 대해서 개념과 동작원리, 구조, DFS와 BFS의 비교, 효율적인 사용처 등 더 자세한 이해를 위해 공부를 해야겠다.
문제
하나부터 열까지 모든 것이 궁금한 개발자 취준생