99클럽 코테 스터디 32일차 TIL + 오늘의 학습 키워드

ㅎㅇ·2024년 8월 22일
0

항해99 TIL

목록 보기
26/33

⭐ 문제

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

🧐 시도

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

static int R, C;
static int[][] map;
static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
static int[] dy = {-1, 0, 1, 1, 1, 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());

    R = Integer.parseInt(st.nextToken());
    C = Integer.parseInt(st.nextToken());
    map = new int[R][C];

    for (int i = 0; i < R; i++) {
        st = new StringTokenizer(br.readLine());
        for (int j = 0; j < C; j++) {
            map[i][j] = Integer.parseInt(st.nextToken());
        }
    }

    int islandCount = 0;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (map[i][j] > 0) {
                dfs(i, j);
                islandCount++;
            }
        }
    }

    System.out.println(islandCount);
}

static void dfs(int x, int y) {
    map[x][y] = 0;

    for (int i = 0; i < 8; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx >= 0 && ny >= 0 && nx < R && ny < C && map[nx][ny] > 0) {
            dfs(nx, ny);
        }
    }
}

}

1.입력 처리:

BufferedReader를 사용하여 입력을 받습니다.
첫 줄에서 R(행)과 C(열)을 입력받아 2차원 맵의 크기를 정합니다.
이후 R*C 크기의 맵을 입력받아 2차원 배열 map에 저장합니다.

2.맵 탐색:

이중 for문을 사용하여 맵의 모든 칸을 순회합니다.
값이 0보다 큰 칸(육지)을 발견하면 dfs 함수를 호출하고 섬 카운트를 증가시킵니다.

3.DFS(깊이 우선 탐색) 구현:

dfs 함수는 현재 위치에서 시작하여 연결된 모든 육지를 탐색합니다.
탐색한 육지는 0으로 바꿔 중복 탐색을 방지합니다.
8방향(상, 하, 좌, 우, 대각선)을 확인하며 연결된 육지를 찾습니다.

4.방향 배열:

dx와 dy 배열을 사용하여 8방향 이동을 구현합니다.

5.결과 출력:

모든 탐색이 끝나면 발견된 섬의 총 개수를 출력합니다.

이 알고리즘의 핵심은 DFS를 사용하여 연결된 육지를 하나의 섬으로 처리하는 것입니다. 한 번 DFS가 호출될 때마다 하나의 섬을 완전히 탐색하고 물(0)로 바꾸기 때문에, DFS 호출 횟수가 곧 섬의 개수가 됩니다.
코드 리뷰:

코드는 전반적으로 잘 구조화되어 있고 가독성이 좋습니다.
DFS를 사용한 접근 방식은 이 문제에 적합합니다.
8방향 탐색을 위한 dx, dy 배열 사용은 효율적입니다.
입력 처리에 BufferedReader와 StringTokenizer를 사용한 것은 좋은 선택입니다.

개선 가능한 점:

예외 처리: 입력값의 유효성 검사를 추가할 수 있습니다.
메모리 사용: 필요하다면 boolean 배열을 사용하여 메모리를 절약할 수 있습니다.
주석: 주요 로직에 대한 간단한 주석을 추가하면 코드 이해도를 높일 수 있습니다.

📝 느낀점

어려워서 지피티 검색하면서 공부

profile
안녕하세요

0개의 댓글