문제
M x N 격자로 이루어진 현수막에 글자가 있다. 각 칸은 검은색(1) 또는 흰색(0)이며, 검은색 칸이 상하좌우 또는 대각선으로 연결되어 있으면 같은 글자(연결 요소)로 본다. 현수막에 있는 글자의 수, 즉 8방향 연결 요소의 개수를 구하는 문제다.
입력
- 첫째 줄: 현수막의 세로 크기 M, 가로 크기 N (1 ≤ M, N ≤ 200)
- 다음 M개의 줄: 현수막 정보 (0: 흰색, 1: 검은색)
출력
글자의 수(8방향 연결 요소의 개수)를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 3 1 1 0 1 0 0 0 0 1 | 2 |
풀이
격자 전체를 순회하며 검은색 칸(1)을 발견하면 BFS를 수행해 8방향으로 연결된 모든 검은색 칸을 방문 처리한다. BFS 호출 횟수가 글자의 개수가 된다.
- 격자를 입력받고, 8방향 이동 배열
dr[],dc[]를 정의한다 (상하좌우 + 대각선 4방향). - 모든 칸을 (0,0)부터 순서대로 확인한다.
- 현재 칸의 값이 1이면
bfs(i, j)를 호출하고ans를 1 증가시킨다. - BFS에서는 현재 칸을 0으로 표시한 뒤, 8방향으로 인접한 칸 중 값이 1인 칸을 큐에 추가하고 즉시 0으로 표시한다.
- 모든 칸을 확인하고 나면
ans가 글자의 총 개수다.
핵심 아이디어: 일반적인 연결 요소 문제(4방향)와 달리, 이 문제는 대각선 연결도 허용하므로 8방향 탐색을 사용한다. BFS 시작 시 방문 처리(map[r][c] = 0)를 즉시 하여 중복 방문을 방지한다.
코드
package com.ssafy.an.day099;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day71BOJ14716현수막BFS {
static int N, M, ans;
static int[] dr = { -1, -1, -1, 0, 0, 1, 1, 1 }, dc = { -1, 0, 1, -1, 1, -1, 0, 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());
ans = 0;
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] == 1)
bfs(i, j);
}
}
System.out.println(ans);
br.close();
}
private static void bfs(int idx, int jdx) {
ans++;
q = new LinkedList<>();
q.add(new int[] { idx, jdx });
while (!q.isEmpty()) {
int[] a = q.poll();
int r = a[0];
int c = a[1];
map[r][c] = 0;
for (int i = 0; i < 8; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (index(nr, nc))
continue;
if (map[nr][nc] == 0)
continue;
map[nr][nc] = 0;
q.add(new int[] { nr, nc });
}
}
}
private static boolean index(int r, int c) {
return r < 0 || c < 0 || r >= N || c >= M;
}
}복잡도
- 시간: O(NM) — 각 칸을 최대 한 번씩 방문
- 공간: O(NM) — BFS 큐에 최대 NM개의 칸이 저장될 수 있음