728x90
문제
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
풀이
그냥 지금까지 많이 풀었던 탐색 문제이다. DFS로 풀었다.
음 뭐랄까 쉬워서 별로 할 말이 없다
https://seokmimmmmmmmm.tistory.com/42?category=1004588
[백준]2468번 안전 영역 - Java
문제 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에
seokmimmmmmmmm.tistory.com
https://seokmimmmmmmmm.tistory.com/71?category=1004588
[백준]2573번 빙산 - Java
문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그..
seokmimmmmmmmm.tistory.com
뭐 이런 문제들이랑 비슷하다
자세한건 주석으로!
코드
// 4963번 섬의 개수
// https://www.acmicpc.net/problem/4963
package BAEKJOON;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Num4963_섬의개수 {
static int W, H;
static int[][] map;
static boolean[][] visited; // 방문 체크 배열
// 8방 탐색 (오른쪽 방향부터 시계 방향)
static int[] dr = {0, 1, 1, 1, 0, -1, -1, -1};
static int[] dc = {1, 1, 0, -1, -1, -1, 0, 1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
StringBuilder sb = new StringBuilder();
while (true) {
st = new StringTokenizer(br.readLine());
W = Integer.parseInt(st.nextToken());
H = Integer.parseInt(st.nextToken());
// 0, 0 받으면 종료
if (W == 0 && H == 0) {
break;
}
map = new int[H][W];
visited = new boolean[H][W];
for (int i = 0; i < H; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < W; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 섬의 개수가 몇개인지 체크
int landCount = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (map[i][j] == 1 && !visited[i][j]) {
solution(i, j); // 연결된 땅(섬) 체크
landCount++; // 섬 개수만큼 증가
}
}
}
sb.append(landCount).append("\n");
}
sb.setLength(sb.length() - 1);
System.out.println(sb.toString());
}
// DFS
private static void solution(int r, int c) {
// 기저조건(방문했거나, 땅이 아니면 return
if (visited[r][c] || map[r][c] == 0) {
return;
}
// 방문 체크
visited[r][c] = true;
for (int i = 0; i < 8; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
// 범위 벗어나면
if (nr < 0 || nr >= H || nc < 0 || nc >= W) {
continue;
}
// 방문하기 전이고 땅이면 solution()
if (map[nr][nc] == 1 && !visited[nr][nc]) {
solution(nr, nc);
}
}
}
}728x90