51 삐약 : 백준 1926| 그림 [바킹독 문제 풀이|BFS|JAVA]

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

1926번: 그림

 

주석 설명 無

package BKD_0x9_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class BOJ_1926 {
    static int n,m;
    static int [][] paper;
    static boolean [][] check; 
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        paper = new int[n][m];

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                paper[i][j]  = Integer.parseInt(st.nextToken());
            }
        }
        check = new boolean[n][m];
        int cnt =0; 
        int max =0; 
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(paper[i][j] ==1 && !check[i][j]){
                    max = Math.max(max,bfs(j,i));
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
        System.out.println(max);
    }

    static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y}); 
        check[y][x] = true; 
        int size =1; 
        while (!q.isEmpty()){
            int[] p = q.poll(); 
            int px = p[0];
            int py = p[1];

            for(int d=0; d<4;d++){
                int nx = px+dx[d];
                int ny = py+dy[d];
                if(nx<0 || ny<0 || nx>m-1 || ny>n-1) continue;
                if(check[ny][nx]) continue;
                if(paper[ny][nx]==1){ 
                    size++; 
                    check[ny][nx]= true; 
                    q.add(new int[]{nx,ny}); 
                }
            }

        }
        return size;
    }
}

 

 

 

---

 

주석 설명 有

 

package BKD_0x9_BFS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/*
 * 단순 BFS 유형의 문제로 이차원 배열의 값이 1인 구간을 탄색하여 최대 탐색 길이와 총 탐색 횟수를 출력하면 된다.
 * 탐색한 길이 == 그림의 크기
 * 탐색 횟수 == 그림 갯수
 */
public class BOJ_1926 {
    static int n,m; // 도화지의 크기 가로 , 세로
    static int [][] paper; // 도화지에 그려져있는 그림의 정보를 저장
    static boolean [][] check; // 해당 위치를 방문했는지 여부를 나타내는 2차원 boolean 배열
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        paper = new int[n][m];
        // 도화지의 크기를 입력받아 빈 도화지를 생성한다.

        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<m;j++){
                paper[i][j]  = Integer.parseInt(st.nextToken());
                // 입력받은 그림 정보를 도화지에 저장한다. (0 | 1)
            }
        }
        check = new boolean[n][m];
        int cnt =0; // 그림의 개수
        int max =0; // 가장 큰 그림의 크기
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                // 도화지 전체를 탐색하며 그림이 그려져 있는데 방문하지 않은 곳을 찾는다.
                if(paper[i][j] ==1 && !check[i][j]){
                    max = Math.max(max,bfs(j,i));
                    // 해당 지점을 기점으로 bfs를 실행하여 해당 점으로부터 그려지는 그림의 크기와 max 값을 비교하여 가장 큰 크기의 그림을 저장한다.
                    cnt++;
                    // 그림의 개수를 카운팅한다.
                }
            }
        }
        System.out.println(cnt);
        System.out.println(max);
    }

    static int bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {x,y}); // 좌표값{x,y}를 저장하는 길이가 2인 정수형 배열을 q에 추가한다 == 탐색을 시작할 도화지에서의 좌표를 q에 추가
        check[y][x] = true; // 동일한 위치를 나타내는 좌표 또한 방문 했음을 표시한다.
        int size =1; // 그림의 크기를 나타내는 변수
        while (!q.isEmpty()){
            int[] p = q.poll(); // 가장 앞에 있는 좌표를 꺼내어 해당 위치를 각 변수에 저장한다.
            int px = p[0];
            int py = p[1];

            for(int d=0; d<4;d++){
                int nx = px+dx[d];
                int ny = py+dy[d];
                // 해당 포지션을 기준으로 상하좌우로 이동하며
                if(nx<0 || ny<0 || nx>m-1 || ny>n-1) continue;
                if(check[ny][nx]) continue;
                if(paper[ny][nx]==1){ // 방문하지 않고 올바른 범위 안에 있는 좌표를 탐색하여
                    size++; // 그림의 크기를 키우고
                    check[ny][nx]= true; // 방문했다는 흔적을 남기고
                    q.add(new int[]{nx,ny}); // 다음 bfs 차례를 위해 q에 추가한다.
                }
            }

        }
        return size;
    }
}

 

 

 

 

• 평소 그래프 문제를 거의 풀어보지 않았기에 bfs, dfs가 무엇인지 어떻게 동작하는 지는 알았지만, 이를 어떻게 적용하여 문제를 해결할 수 있는지에 대한 고민이 어려웠던 것 같다.
• 텍스트로 마주하는 문제와 실제 접근하는 방법에 대해서 많이 연습해야 할 것 같다. 
• 문제 풀이의 감을 익히기 위해 참고 블로그의 코드를 해석하며 진행 방법을 파악하였다. 
• 아자뵵

 

 

참고 url : https://loosie.tistory.com/511

[BOJ] 백준 1926번 그림 (Java)