[Gold 5] [Java] 현수막 (14716 번)

<현수막>

문제 설명

ANT가 처음 알고리즘 대회를 개최하게 되면서 현수막을 내걸었다.

저번 학기 영상처리 수업을 듣고 배웠던 지식을 최대한 응용 해보고 싶은 혁진이는 이 현수막에서 글자가 몇 개인지 알아보는 프로그램을 만들려 한다.

혁진이는 우선 현수막에서 글자인 부분은 1, 글자가 아닌 부분은 0으로 바꾸는 필터를 적용하여 값을 만드는데 성공했다.

그런데 혁진이는 이 값을 바탕으로 글자인 부분 1이 상, 하, 좌, 우, 대각선으로 인접하여 서로 연결되어 있다면 한 개의 글자라고 생각만 하였다.

혁진이가 필터를 적용하여 만든 값이 입력으로 주어졌을 때, 혁진이의 생각대로 프로그램을 구현하면 글자의 개수가 몇 개인지 출력하여라.

 

제한 사항

 

입력

첫 번째 줄에는 현수막의 크기인 M와 N가 주어진다. (1 ≤ M, N ≤ 250)

두 번째 줄부터 M+1 번째 줄까지 현수막의 정보가 1과 0으로 주어지며, 1과 0을 제외한 입력은 주어지지 않는다.

 

출력

혁진이의 생각대로 프로그램을 구현했을 때, 현수막에서 글자의 개수가 몇 개인지 출력하여라.

 

내 생각

BFS탐색의 기본이 되는 문제라고 생각했습니다. 다만 기존엔 4방향 탐색을 했다면 이번엔 8방향을 탐색할 수 있는지 물어보는 것 같았습니다. 8방향도 어렵게 생각하지말고 대각선 방향만 추가해주고 똑같이 BFS 탐색을 시작하면 됩니다. 

0,0 부터 탐색을 시작해 인접한 곳에 1이 있을 경우 visit처리를 모두 해줄 것입니다. 큐가 다 비어질때가지 탐색이 완료된다면 answer값을 한 개씩 증가 시켜주면 될 것입니다. 

 

작성 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    static int N, M, answer;
    static int[][] map;
    static int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {-1, 0, 1, 1, 1, 0, -1, -1};
    static Queue<Point> q;
    static boolean[][] visit;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input;
        input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        map = new int[M][N];
        visit = new boolean[M][N];
        q = new LinkedList<Point>();
        // 현수막 입력
        for (int row = 0; row < M; row++) {
            input = br.readLine().split(" ");
            for (int col = 0; col < N; col++) {
                map[row][col] = Integer.parseInt(input[col]);
            }
        }
        // 0, 0부터 탐색 시작
        for (int row = 0; row < M; row++) {
            for (int col = 0; col < N; col++) {
                if (!visit[row][col] && map[row][col] == 1) {
                    q.add(new Point(row, col));
                    bfs();
                }
            }
        }
        
        System.out.println(answer);
        
    }
 
    private static void bfs() {
        while (!q.isEmpty()) {
            Point point = q.poll();
            int x = point.x;
            int y = point.y;
            // 8방향의 탐색
            for (int i = 0; i < 8; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if (0 <= nx && nx < M && 0 <= ny && ny < N) {
                    if (!visit[nx][ny] && map[nx][ny] == 1) {
                        visit[nx][ny] = true;
                        q.add(new Point(nx, ny));
                    }
                }
            }
            
        }    // End of while
        
        // 탐색 종료시 answer 값 증가
        answer++;
    }
 
}