728x90
반응형
https://www.acmicpc.net/problem/4963
4963번: 섬의 개수
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도
www.acmicpc.net
|
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
88
89
90
|
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static int[][] arr;
public static int[][] visit;
public static int count = 0;
public static ArrayList<Integer> c = new ArrayList<Integer>();
public static int[] dirX = { -1, 1, 0, 0 };
public static int[] dirY = { 0, 0, -1, 1 };
public static int[] dirZ = { -1, -1, 1, 1 };
public static int[] dirZ2 = { -1, 1, -1, 1 };
public static void dfs(int i, int j, int w, int h) {
visit[i][j] = 1;
for (int i1 = 0; i1 < 4; i1++) {
int X = i + dirX[i1];
int Y = j + dirY[i1];
int Z1 = i + dirZ[i1];
int Z2 = j + dirZ2[i1];
if (Z1 >= 0 && Z1 < h && Z2 >= 0 && Z2 < w) {
if (arr[Z1][Z2] == 1 && visit[Z1][Z2] == 0) {
dfs(Z1, Z2, w, h);
}
}
if (X >= 0 && X < h && Y >= 0 && Y < w) {
if (arr[X][Y] == 1 && visit[X][Y] == 0) {
dfs(X, Y, w, h);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (true) {
count = 0;
int w = sc.nextInt();
int h = sc.nextInt();
if (w == 0 && h == 0) {
break;
} else {
arr = new int[h][w];
visit = new int[h][w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
arr[i][j] = sc.nextInt();
visit[i][j] = 0;
}
}
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (arr[i][j] == 1 && visit[i][j] == 0) {
// System.out.println(i + " " + j);
count++;
dfs(i, j, w, h);
}
}
}
c.add(count);
}
}
for (int i : c) {
System.out.println(i);
}
}
}
|
cs |
https://we1cometomeanings.tistory.com/164
[java 백준] 실버 1/2667번 단지번호 붙이기
https://www.acmicpc.net/problem/2667 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번
we1cometomeanings.tistory.com
이 문제에서 대각선만 추가된 것이다. 나는 Z1,Z2로 놓고 풀었다!
728x90
반응형
'알고리즘 > 그래프' 카테고리의 다른 글
| [java 백준] 실버 1/7576번 토마토 (0) | 2021.10.03 |
|---|---|
| [java 백준]실버 1/ 7569번 토마토 (0) | 2021.10.03 |
| [java 백준] 실버 1/2667번 단지번호 붙이기 (0) | 2021.09.29 |
| [java 백준] 실버 4/2331번 반복수열 (0) | 2021.09.26 |
| [java 백준]실버 2/ 10451번 순열 사이클 (0) | 2021.09.26 |
댓글