제출 코드
- 사용 알고리즘 :
BFS
처음에 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
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
package showmethecode230114;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Test_b { // 도넛 행성
static int N, M, total;
static int[][] map;
static int[] di = {-1, 0, 1, 0};
static int[] dj = {0, 1, 0, -1};
static class Node{
int i, j;
Node(int i, int j){
this.i = i;
this.j = j;
}
}
static void dfs(int i, int j, int cnt) {
for(int d=0; d<4; d++) {
int ni = (i+di[d]+N) % N;
int nj = (j+dj[d]+M) % M;
if(map[ni][nj]==0) {
map[ni][nj] = cnt;
total--;
dfs(ni, nj, cnt);
}
}
}
static void bfs(int i, int j, int cnt) {
Queue<Node> q = new LinkedList<Node>();
q.add(new Node(i, j));
while(!q.isEmpty()) {
int size = q.size();
for(int s=0; s<size; s++) {
Node now = q.poll();
for(int d=0; d<4; d++) {
int ni = (now.i+di[d]+N) % N;
int nj = (now.j+dj[d]+M) % M;
if(map[ni][nj]==0) {
map[ni][nj] = cnt;
total--;
q.add(new Node(ni, nj));
}
}
}
}
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
Queue<Node> queue = new LinkedList<Node>();
for(int i=0; i<N; i++) {
st = new StringTokenizer(br.readLine());
for(int j=0; j<M; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
if(map[i][j]==0) queue.add(new Node(i, j));
}
}
int cnt=0, total=queue.size();
while(!queue.isEmpty() && total>0) {
Node now = queue.poll();
if(map[now.i][now.j]==0) {
total--;
map[now.i][now.j] = ++cnt+1;
bfs(now.i, now.j, cnt+1);
// dfs(now.i, now.j, cnt+1);
}
}
System.out.println(cnt);
}
}