문제
N×M 격자가 상하좌우로 이어진 도넛(토러스) 형태이다. 0은 빈 칸, 1은 장애물일 때 빈 칸으로 이루어진 연결 영역의 수를 구하라.
입력
첫째 줄에 N, M, 이후 N×M 격자가 주어진다.
출력
연결 영역의 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 0 1 0 0 0 0 0 1 0 | 1 |
풀이
BFS 플러드 필로 연결 영역을 센다. 도넛 형태이므로 좌표를 모듈러 연산으로 처리한다.
- 모든 칸을 순회하며 값이 0인 칸에서 BFS를 시작한다
- BFS에서 4방향 이동 시
(r + dr + N) % N,(c + dc + M) % M으로 좌표를 순환시킨다 - 방문한 칸을 ans 값으로 표시하여 재방문을 방지한다
- BFS를 시작할 때마다 ans를 증가시킨다
핵심 아이디어: 일반 격자의 플러드 필과 동일하지만, 경계에서 반대편으로 이어지는 도넛 구조를 모듈러 연산으로 처리한다.
코드
package day399;
import java.io.*;
import java.util.*;
public class Day380BOJ27211도넛행성 {
static int N, M, ans = 0;
static int[] dr = { -1, 1, 0, 0 }, dc = { 0, 0, -1, 1 };
static int[][] map;
static Queue<int[]> q;
public static void main(String[] args) throws Exception {
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];
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());
}
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (map[i][j] == 0)
bfs(i, j);
System.out.println(ans);
br.close();
}
private static void bfs(int idx, int jdx) {
ans++;
q = new LinkedList<>();
map[idx][jdx] = ans;
q.offer(new int[] { idx, jdx });
while (!q.isEmpty()) {
int[] cur = q.poll();
for (int dir = 0; dir < 4; dir++) {
int nr = (cur[0] + dr[dir] + N) % N;
int nc = (cur[1] + dc[dir] + M) % M;
if (map[nr][nc] == 0) {
map[nr][nc] = ans;
q.offer(new int[] { nr, nc });
}
}
}
}
}복잡도
- 시간: O(N * M) - 각 칸을 최대 한 번 방문
- 공간: O(N * M) - 격자 및 BFS 큐