[Silver II] 섬의 개수 - 4963
성능 요약
메모리: 31412 KB, 시간: 316 ms
분류
그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
제출 일자
2023년 12월 10일 16:09:48
문제 설명
정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.
한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.
두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
출력
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.
풀이 방법
1. 섬에서 다른 섬으로 방문 할 수 있는 곳은 상,하,좌,우, 왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래라는 걸 생각
2. map에 대한 입력이 w,h 순서로 입력
3. for문을 돌려 섬이면서 방문하지 않았다면 result를 증가 시키고 bfs메소드
4. bfs메소드에서는 해당 섬에서 방문 할 수 있는 섬을 전부 방문체크
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Main {
static int[][] map;
static boolean[][] visit;
static StringBuilder sb = new StringBuilder();
static int[] dirX = {0, 0, -1, 1, -1, -1, 1, 1};
static int[] dirY = {-1, 1, 0, 0, 1, -1, 1, -1};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int h, w;
while (true) {
// h, w 입력
h = sc.nextInt();
w = sc.nextInt();
// 둘 다 0이면 종료
if (h == 0 && w == 0) {
break;
}
// 섬과 바다를 입력 받을 map
map = new int[w][h];
// 방문 확인을 위한 visit
visit = new boolean[w][h];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
map[i][j] = sc.nextInt();
}
}
int result = 0;
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[i].length; j++) {
// map가 섬이고 방문하지 않았다면 result 증가 후 섬 방문 확인
if (map[i][j] == 1 && !visit[i][j]) {
result++;
bfs(i, j);
}
}
}
sb.append(result).append("\n");
}
System.out.println(sb.toString());
}
private static void bfs(int x, int y) {
Queue<int[]> queue = new LinkedList<>();
visit[x][y] = true;
queue.offer(new int[] {x, y});
while (!queue.isEmpty()) {
// 현재 섬의 위치
int cur[] = queue.poll();
int curX = cur[0];
int curY = cur[1];
// 주변 상,하,좌,우,각 대각를 기준으로 확인
for (int i = 0; i < dirX.length; i++) {
int nextX = curX + dirX[i];
int nextY = curY + dirY[i];
// 배열의 크기 밖이라면 continue;
if (nextX < 0 || nextX >= map.length || nextY < 0 || nextY >= map[nextX].length) {
continue;
}
// 방문할 곳이 바다거나 방문했다면 continue;
if (map[nextX][nextY] == 0 || visit[nextX][nextY]) {
continue;
}
visit[nextX][nextY] = true;
queue.offer(new int[] {nextX, nextY});
}
}
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 10431번 : 줄세우기 Silver5(실버5) - JAVA[자바] (1) | 2023.12.11 |
---|---|
[백준] 2331번 : 반복수열 Silver4(실버 4) - JAVA[자바] (1) | 2023.12.10 |
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바] (1) | 2023.12.10 |
[백준] 10819번 : 차이를 최대로 Silver2(실버2) - JAVA[자바] (0) | 2023.12.01 |
[백준] 11724번 : 연결 요소의 개수 Silver2(실버2) - JAVA[자바] (0) | 2023.11.30 |