[BOJ] 4963. 섬의 개수 - BFS
제출일 : 2019-10-07
문제 풀이 시간 : 30M
난이도 : ★★☆
Problem
Input
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.
둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.
입력의 마지막 줄에는 0이 두 개 주어진다.
Output
각 테스트 케이스에 대해서, 섬의 개수를 출력한다.
Example
input
1 1
0
2 2
0 1
1 0
3 2
1 1 1
1 1 1
5 4
1 0 1 0 0
1 0 0 0 0
1 0 1 0 1
1 0 0 1 0
5 4
1 1 1 0 1
1 0 1 0 1
1 0 1 0 1
1 0 1 1 1
5 5
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0
output
0
1
1
3
1
9
Solution & Inpression
1차 시도 :
메모리 초과
private static void solve(int i, int j, int cnt) {
int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { i, j });
while (!q.isEmpty()) {
int[] tmp = q.poll();
map[tmp[0]][tmp[1]] = cnt;
for (int k = 0; k < 8; k++) {
int r = tmp[0] + dr[k];
int c = tmp[1] + dc[k];
if (range(r, c)) {
if (map[r][c] == -1) {
q.offer(new int[] { r, c });
}
}
}
}
}
방문처리
를 큐에서 값을 빼올때 처리하였다.
이렇게 작성하였다면 이미 큐에 담겨있지만 방문이 안되었다 판단하기 때문에 불필요하게 큐에 값이 들어가게 되는 현상이 발생하여 메모리초과가 발생한다.
방문처리를 아래와 같은 방법으로 수정하여 메모리 초과는 발생하지 않았다.
Code
언어 : JAVA
메모리 : 32,984 kb
실행시간 : 328 ms
import java.io.*;
import java.util.*;
public class Main_백준_4963_섬의개수 {
static int W, H;
static int[][] map;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
while (true) {
W = sc.nextInt();
H = sc.nextInt();
if (W == 0 && H == 0)
break;
map = new int[H][W];
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
int tmp = sc.nextInt();
if (tmp == 1)
map[i][j] = -1;
else
map[i][j] = tmp;
}
}
int cnt = 0;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
if (map[i][j] == -1) {
solve(i, j, ++cnt);
}
}
}
System.out.println(cnt);
// for(int[] is : map)
// System.out.println(Arrays.toString(is));
} // end of tc
sc.close();
}// end of main
private static void solve(int i, int j, int cnt) {
int[] dr = { -1, 1, 0, 0, 1, 1, -1, -1 };
int[] dc = { 0, 0, -1, 1, 1, -1, -1, 1 };
Queue<int[]> q = new LinkedList<>();
q.offer(new int[] { i, j });
map[i][j] = cnt;
while (!q.isEmpty()) {
int[] tmp = q.poll();
for (int k = 0; k < 8; k++) {
int r = tmp[0] + dr[k];
int c = tmp[1] + dc[k];
if (range(r, c)) {
if (map[r][c] == -1) {
q.offer(new int[] { r, c });
map[r][c] = cnt;
}
}
}
}
}
private static boolean range(int r, int c) {
if (0 <= r && r < H && 0 <= c && c < W)
return true;
return false;
}
}
'Problem > BOJ' 카테고리의 다른 글
[BOJ] 1157. 단어공부 - Array (0) | 2019.10.08 |
---|---|
[BOJ] 17472. 다리 만들기2 - Prim (0) | 2019.10.07 |
[BOJ] 4963. 섬의 개수 - DFS (0) | 2019.10.07 |
[BOJ] 5427. 불 - BFS (0) | 2019.10.06 |
[BOJ] 6593. 상범빌딩 - BFS (0) | 2019.10.03 |