코딩테스트-알고리즘/백준 BOJ
[백준 BOJ/Silver II] 4963번 : 섬의 개수
닉네임생각즁
2024. 1. 18. 23:27
https://www.acmicpc.net/problem/4963
import java.util.Scanner;
public class Main {
static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
static int result; // 결과
static int w; // 너비, j
static int h; // 높이, i
static int[][] map; // 지도
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while(true) {
result = 0;
w = sc.nextInt();
h = sc.nextInt();
map = new int[h][w];
if (w == 0 & h == 0) break; // 0 0 나오면 종료
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
map[i][j] = sc.nextInt();
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if(map[i][j] == 1) {
dfs(i, j);
result++;
}
}
}
System.out.println(result);
}
}
static void dfs(int x, int y) {
map[x][y] = 0;
for(int i=0; i<8; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if(nextX>=0 && nextX < h && nextY>=0 && nextY < w) {
if(map[nextX][nextY] == 1) {
dfs(nextX, nextY);
}
}
}
}
}
이번 문제는 대각선까지 포함하기 때문에 확인해야할 부분이 더 늘어난다
그려서 확인해보면 이렇고 이걸 dx, dy로 넣어서 다음 x와 y를 계산해주면 된다
이어지는것들을 모두 타고타고가며 확인해주고, 돌아온 후 다음 범위로 넘어가며 답을 더해주면 완성!