백준 4963번: 섬의 개수[JAVA]
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
[정답코드]
import java.io.*;
import java.util.*;
public class Main {
static int w;
static int h;
static int[][] map;
static int[] dx = {0, 0, 1, -1, -1, 1, -1, 1};
static int[] dy = {1, -1, 0, 0, -1, 1, 1, -1};
static boolean[][] visit;
static int count; // 섬의 개수
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
while (true) { // w와 h가 0이 되면 종료
st = new StringTokenizer(br.readLine(), " ");
// w 지도의 너비, h 지도의 높이
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
// 0이 되면 종료
if (w == 0 && h == 0) {
break;
}
//지도 배열 선언
map = new int[h][w];
//방문한 곳 배열 선언
visit = 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());
}
}
count = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (map[i][j] == 1 && !visit[i][j]) { // 섬이 있고 방문하지 않았다면 bfs 함수실행
bfs(i, j);
count++;
}
}
}
System.out.println(count);
}
}
public static void bfs(int x, int y) {
visit[x][y] = true;
//8방탐색
for (int i = 0; i < 8; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//지도범위 안에 있을 경우
if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
if (map[nx][ny] == 1 && !visit[nx][ny]) { //8방탐색한곳이 방문하지않고, 섬이 존재할경우
bfs(nx, ny);
}
}
}
}
}
[설명]
지도를 설정한 후 지도의 시작지점부터 탐색을 시작한다. 섬이있는 자리 이면서 visit가 false 일경우 bfs 함수를 실행한다.
bfs 함수는 섬이있는 자리이면서 visit가 false 인 자리를 기준으로 8방 탐색을 실행한다. 8방 탐색을 실행할때 탐색한자리에 에 또 섬이있고 방문한적이 없는 자리면 그 자리를 기준으로 다시 bfs함수를 실행한다.
'코딩테스트' 카테고리의 다른 글
| 백준 7576번: 토마토[JAVA] (1) | 2023.11.03 |
|---|---|
| 백준 11724번: 연결 요소의 개수[JAVA] (1) | 2023.11.03 |
| 백준 14888번: 연산자 끼워넣기[JAVA] (1) | 2023.10.27 |
| 백준 1914번: 하노이 탑[JAVA] (1) | 2023.10.27 |
| 백준 17609번: 회문[JAVA] (1) | 2023.10.21 |
