백준 4963번 : 섬의 개수 (범위 탐색 개수)
앞선 백준 2468번 : 안전 영역 포스트에서 말했듯이 간단하게 작성할 것이다.
이번 문제는 1=땅, 0=바다가 표현된 h*w 크기의 그래프가 여러개 주어질 때 각각 섬은 몇 개가 있는지 리턴하는 문제이다.
여기서 조심해야할 것이, 땅은 상하좌우 뿐만 아니라 대각선으로도 연결되었다고 판단해야한다.
즉, 이 문제를 기록하는 이유는 “대각선 방향” 때문이다.
각설하고, 테스트 케이스가
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
이런 식으로 여러 개의 그래프가 입력되기 때문에 이 데이터에 대한 핸들링이 우선이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
while (w+h > 0) {
arr = 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++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (arr[i][j] == 1 && !visited[i][j]) {
count++;
// dfs(i, j);
bfs(i,j);
}
}
}
sb.append(count).append('\n');
count = 0;
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
}
System.out.println(sb);
}
여러 번 입력되는 w와 h, 그리고 그래프를 한꺼번에 핸들링하기 위해 while 문의 조건으로 가장 처음 입력 받는 w와 h를 활용해 w+h가 0 이상이면 반복되게끔 설정해두었다.
이후 while 반복문 내부에서 각 그래프를 생성하고 해당 그래프를 탐색하며, 결과값을 sb에 합치고서 다시 w와 h를 입력받는다.
문제에서 주어지듯이 마지막에 0과 0이 입력되면 0과 같아지기 때문에 while문은 종료된다.
이 문제에서는 사실 위의 로직을 작성하는데에 시간이 조금 걸리는 것 외에는 큰게 없다.
아래의 DFS와 BFS를 보면 다른 문제와 완벽히 동일한 로직이다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public static void dfs(int x, int y) {
visited[x][y] = true;
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 (arr[nx][ny] == 1 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
}
public static void bfs(int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 8; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
대각선 때문에 무언가 크게 달라질 것 같지만 전혀 그렇지 않다.
단순히 방향이 8방향으로 늘어나는 것이기 때문에 탐색 내부 반복문을 실행시킬 때 횟수만 증가시키면 된다.
메인 로직과 탐색 로직 둘 다 “대각선” 관련해서 무언가를 추가해줄 필요는 없다.
단순히 방향이기 때문에 해당 방향에 대한 설정만 제대로 해주면 된다.
1
2
3
4
5
6
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1}; // 좌, 우, 상, 하 + 좌상, 우상, 좌하, 우하
static int[] dy = {0, 1, 0, -1, -1, 1, -1, 1}; // 좌, 우, 상, 하 + 좌상, 우상, 좌하, 우하
static StringBuilder sb = new StringBuilder();
static int w, h, count = 0;
위 값들이 클래스의 멤버 변수들이다.
좌표 탐색 문제의 방향에 대한 설정으로 대각선을 포함해주면 된다.
기본적인 상하좌우 외에 좌상, 우상, 좌하, 우하를 추가했다.
이로써 8방향, 대각선 포함하는 탐색이 가능해진다.
전체 소스 코드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int[][] arr;
static boolean[][] visited;
static int[] dx = {-1, 0, 1, 0, -1, -1, 1, 1}; // 좌, 우, 상, 하 + 좌상, 우상, 좌하, 우하
static int[] dy = {0, 1, 0, -1, -1, 1, -1, 1}; // 좌, 우, 상, 하 + 좌상, 우상, 좌하, 우하
static StringBuilder sb = new StringBuilder();
static int w, h, count = 0;
public static void main(String[] args) throws java.io.IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
while (w+h > 0) {
arr = 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++) {
arr[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (arr[i][j] == 1 && !visited[i][j]) {
count++;
// dfs(i, j);
bfs(i,j);
}
}
}
sb.append(count).append('\n');
count = 0;
st = new StringTokenizer(br.readLine());
w = Integer.parseInt(st.nextToken());
h = Integer.parseInt(st.nextToken());
}
System.out.println(sb);
}
public static void dfs(int x, int y) {
visited[x][y] = true;
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 (arr[nx][ny] == 1 && !visited[nx][ny]) {
dfs(nx, ny);
}
}
}
}
public static void bfs(int x, int y) {
visited[x][y] = true;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int i = 0; i < 8; i++) {
int nx = cur[0] + dx[i];
int ny = cur[1] + dy[i];
if (nx >= 0 && ny >= 0 && nx < h && ny < w) {
if (arr[nx][ny] == 1 && !visited[nx][ny]) {
q.offer(new int[]{nx, ny});
visited[nx][ny] = true;
}
}
}
}
}
}
위에서 아래로 순서대로 BFS, DFS 탐색이다.
대각선 탐색 방향은 현재 포스트를 참조하자.
그런데 항상 생각하는거지만 왠만한 문제들이 DFS 탐색이 더 효율적인데 왜 BFS 탐색 카테고리에 있는지 모르겠다.
이 블로그는 저작권자의 CC BY 4.0 라이센스를 따릅니다.