[BOJ] 14716 현수막

현수막

풀이

• 1과 0으로 이루어진 input이 주어지고, 1이 상하좌우,대각선방향으로 연결되어 있으면 하나의 글자로 보기로 했으므로, 8방탐색 bfs 로 풀었다.
• 특별한 것 없이 기본 풀이로 풀었음.

코드

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

public class Main {
    static int[][] map;
    static boolean[][] visited;
    static int[] dx ={-1,1,0,0,-1,-1,1,1};
    static int[] dy = {0,0,-1,1,-1,1,-1,1};
    static int answer = 0;
    static int N,M;
    public static void main(String[] args) throws Exception{

        //상하좌우대각선
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());
        map = new int[M][N];
        visited = new boolean[M][N];
        for(int i=0;i<M;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0;i<M;i++){
            for(int j=0;j<N;j++){
                if(map[i][j]==1 && !visited[i][j]){
                    bfs(i,j);
                    answer++;
                }
            }
        }
        System.out.println(answer);

    }
    private static void bfs(int x, int y){
        visited[x][y] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{x,y});
        while(!queue.isEmpty()){
            int[] cur = queue.poll();
            for(int i=0;i<8;i++){
                int nx = cur[0]+dx[i];
                int ny = cur[1]+dy[i];
                if(nx>=0 && nx<M && ny>=0 && ny<N && map[nx][ny]==1 &&
                !visited[nx][ny]
                ){
                    visited[nx][ny] = true;
                    queue.add(new int[]{nx,ny});
                }
            }
        }
    }
}