BOJ 14716 - 현수막 [Java]

 

 

문제

https://www.acmicpc.net/problem/14716

0과 1로만 이루어진 2차원 격자가 주어진다.

1이 격자 상에서 인접한 8방향으로 연결되어있다면 연결 요소 전체를 한 글자로 볼 때,

총 연결 요소의 수를 구하는 문제이다.

 

풀이

격자를 순회하며 1을 만날 때마다 BFS로 연결 요소를 모두 방문처리한 후 글자 수를 올려주었다.

 

import java.util.*;
import java.io.*;

class Node{
    int x;
    int y;
    Node(int x, int y){
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static StringTokenizer st;
    static int nextInt() { return Integer.parseInt(st.nextToken()); }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        st = new StringTokenizer(br.readLine());
        int N = nextInt(), M = nextInt();

        int[][] arr = new int[N][M];
        int[] dx = {-1,-1,-1,0,0,1,1,1};
        int[] dy = {-1,0,1,-1,1,-1,0,1};

        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<M;j++) arr[i][j] = nextInt();
        }

        boolean[][] vis = new boolean[N][M];
        int ans = 0;
        for(int i=0;i<N;i++) for(int j=0;j<M;j++) if(!vis[i][j] && arr[i][j]==1) {
            Queue<Node> Q = new LinkedList<>();
            Q.offer(new Node(i,j));
            vis[i][j] = true;
            while(!Q.isEmpty()) {
                Node n = Q.poll();
                for(int k=0;k<8;k++) {
                    int xx = n.x+dx[k], yy = n.y+dy[k];
                    if(xx<0 || xx>=N || yy<0 || yy>=M || vis[xx][yy] || arr[xx][yy]==0) continue;
                    Q.offer(new Node(xx,yy));
                    vis[xx][yy] = true;
                }
            }
            ans++;
        }
        bw.write(ans+"\n");

        bw.close();
    }

}