👀 문제
https://www.acmicpc.net/problem/4963
👊 도전
1. 설계
- DFS를 이용하여 상하좌우 대각선으로 이동한다.
- 연결되지 않은 섬의 개수들을 출력한다.
2. 구현 (성공 코드)
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
import java.util.Scanner;
/**
* @author HEESOO
*
*/
public class Main {
static int w, h;
static int[][] array;
static boolean[][] visit;
public static void dfs(int x, int y) {
int[] dotX= {0,1,1,1,0,-1,-1,-1};
int[] dotY= {1,1,0,-1,-1,-1,0,1};
for(int i=0;i<8;i++) {
int xx=x+dotX[i];
int yy=y+dotY[i];
if(0<=xx&&xx<w && 0<=yy&&yy<h) {
if(array[xx][yy]==1&&!visit[xx][yy]) {
visit[xx][yy]=true;
dfs(xx,yy);
}
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner scan = new Scanner(System.in);
while(true) {
w=scan.nextInt();
h=scan.nextInt();
if(w==0&&h==0) break;
array=new int[w][h];
visit=new boolean[w][h];
for(int i=0;i<h;i++) {
for(int j=0;j<w;j++) {
array[j][i]=scan.nextInt();
}
}
int cnt=0;
for(int i=0;i<w;i++) {
for(int j=0;j<h;j++) {
if(array[i][j]==1&&!visit[i][j]) {
cnt++;
dfs(i, j);
}
}
}
System.out.println(cnt);
}
}
}
3. 결과
🤟 성공 🤟
for문에서 dotX, dotY 길이가 8인데 6으로 설정해서 틀렸다.
4. 설명
- DFS를 이용한다
- 노드 이동은 상하좌우 대각선 총 8가지 방법이 가능하다.
- dotX, dotY 배열을 이용해 이동 인덱스를 생성한 후, 다음 방문할 노드의 좌표 xx, yy를 구한다.
- xx, yy가 인덱스 범위를 벗어나지 않고 해당 위치가 섬이고, 방문하지 않은 곳이라면 재귀호출로 방문한다.
- 섬은 떨어져 있을 수 있으므로 main에서 2중for문을 통해 모든 노드들을 체크해야한다. i, j위치가 섬인데 방문하지 않은 곳이라면 cnt++한 후 방문한다.
- cnt가 연결되지 않은 섬의 개수를 나타낸다.