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);
}
}
}
}
BufferedReader를 사용하여 입력을 받습니다.
첫 줄에서 R(행)과 C(열)을 입력받아 2차원 맵의 크기를 정합니다.
이후 R*C 크기의 맵을 입력받아 2차원 배열 map에 저장합니다.
이중 for문을 사용하여 맵의 모든 칸을 순회합니다.
값이 0보다 큰 칸(육지)을 발견하면 dfs 함수를 호출하고 섬 카운트를 증가시킵니다.
dfs 함수는 현재 위치에서 시작하여 연결된 모든 육지를 탐색합니다.
탐색한 육지는 0으로 바꿔 중복 탐색을 방지합니다.
8방향(상, 하, 좌, 우, 대각선)을 확인하며 연결된 육지를 찾습니다.
dx와 dy 배열을 사용하여 8방향 이동을 구현합니다.
모든 탐색이 끝나면 발견된 섬의 총 개수를 출력합니다.
이 알고리즘의 핵심은 DFS를 사용하여 연결된 육지를 하나의 섬으로 처리하는 것입니다. 한 번 DFS가 호출될 때마다 하나의 섬을 완전히 탐색하고 물(0)로 바꾸기 때문에, DFS 호출 횟수가 곧 섬의 개수가 됩니다.
코드 리뷰:
코드는 전반적으로 잘 구조화되어 있고 가독성이 좋습니다.
DFS를 사용한 접근 방식은 이 문제에 적합합니다.
8방향 탐색을 위한 dx, dy 배열 사용은 효율적입니다.
입력 처리에 BufferedReader와 StringTokenizer를 사용한 것은 좋은 선택입니다.
개선 가능한 점:
예외 처리: 입력값의 유효성 검사를 추가할 수 있습니다.
메모리 사용: 필요하다면 boolean 배열을 사용하여 메모리를 절약할 수 있습니다.
주석: 주요 로직에 대한 간단한 주석을 추가하면 코드 이해도를 높일 수 있습니다.
어려워서 지피티 검색하면서 공부