[백준/JAVA] 14716번: 현수막

📖 문제

14716번: 현수막

 

 

 

💡  풀이 방식

• BFS

1. 격자의 모든 칸을 입력받는다.

2. 격자의 모든 점을 돌면서, 방문한 적 없는 글자(1)인 부분에서 BFS를 수행하고, 그 수행 횟수를 구한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {-1,1,0,0, -1,-1,1,1};    // 8방향 (상하좌우 + 대각선 4방향)
    static int[] dy = {0,0,-1,1, -1,1,-1,1};
    
    static int M,N;
    static int[][] map;
    static boolean[][] visited;
    static int cnt = 0;
    
    public static void main(String[] args) throws IOException {
        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(!visited[i][j] && map[i][j] == 1) {    // 방문한 적 없는 글자인 부분 탐색
                    bfs(i, j);
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt);
    }
    
    // BFS: 글자 한 개 연결짓기
    private static void bfs(int x, int y) {    
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {x, y});
        visited[x][y] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            for(int d = 0 ; d < 8 ; d++) {
                int nx = now[0] + dx[d];
                int ny = now[1] + dy[d];
                
                if(nx < 0 || nx >= M || ny < 0 || ny >= N)  continue;
                if(!visited[nx][ny] && map[nx][ny] == 1) {
                    visited[nx][ny] = true;
                    q.add(new int[] {nx, ny});
                }
            }
        }
    }
}
 

 

 

 

➕ 다른 풀이 방식

DFS로도 풀 수 있다

[Java] 백준 14716번 : 현수막

 

---

 

1회독	2회독	3회독	4회독	5회독
V