[백준] 🥈 1926 그림

📌 난이도

🥈 Silver 1

📌 문제

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

📌 풀이

코딩테스트에서 가장 어렵다는 BFS관련 알고리즘에 대해서 공부한 다음 연관된 문제를 찾아보았다.
근데 BFS 문제는 난이도가 브론즈는 커녕 실버2부터 시작했다.
떨리는 마음으로 처음으로 문제를 풀어보았다.

처음에는 boolean[][] drawPaper가 아닌 class paper라는 클래스를 만들어서 int isCheck와 int isDraw를 넣어서 구별을 하려고 했었다.
그런데 생각해보니 굳이 둘을 구별할 필요없이, 확인한 곳은 빈곳으로 바꿔버려서 처리해버리면 용량도 아끼고, 속도도 빨라질 것 같아서 다음과 같이 개선을 하였다.

기본적으로 배열의 모든곳에 그림이 그려져 있는지(true) 확인을 하면서, 그림이 그려져 있으면(true), 그곳의 그림을 지운후(false), Queue에 위치를 저장하고, currnetArea를 1로 초기화하고, paperCount에 1을 더해주었다. 이후 while(!q.isEmpty())문을 통해 그림이 있던 위치에 접해있는 상하좌우를 비교하기 위하여, DR/DC를 사용하여 다음 위치를 구해주었다.
이후 그 위치에 그림이 그려져(true)있으면 빈곳(false)으로 바꾸고, 그 위치를 또다시 Queue에 넣어주었다.
이후 whlie문이 끝나면 Math.max를 통하여 currentArea와 maxArea를 비교하였다.

처음으로 푼 BFS 문제였지만, 생각보다 쉽게 풀려서 기분이 좋았다.

📌 Code

package BFS;

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

public class N1926 {
    static boolean[][] drawPaper;

    static final int[] DR = {0, -1, 0, 1};
    static final int[] DC = {1, 0, -1, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        drawPaper = new boolean[n][m];

        Queue<Integer[]> q = new LinkedList<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                if (Integer.parseInt(st.nextToken()) == 1) {
                    drawPaper[i][j] = true;
                } else {
                    drawPaper[i][j] = false;
                }
            }
        }
        int maxArea = 0;
        int currentArea = 0;
        int paperCount = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (drawPaper[i][j]) {
                    drawPaper[i][j] = false;
                    q.add(new Integer[]{i, j});
                    currentArea = 1;
                    paperCount += 1;
                }
                while (!q.isEmpty()) {
                    Integer[] cur = q.poll();
                    for (int k = 0; k < 4; k++) {
                        int nextR = cur[0] + DR[k];
                        int nextC = cur[1] + DC[k];
                        if (nextR < 0 || nextR >= n || nextC < 0 || nextC >= m ||
                                !drawPaper[nextR][nextC]) {
                            continue;
                        }
                        drawPaper[nextR][nextC] = false;
                        q.add(new Integer[]{nextR, nextC});
                        currentArea += 1;
                    }
                }
                maxArea = Math.max(currentArea, maxArea);
            }
        }
        System.out.println(paperCount + " " + maxArea);
    }
}

package (이름); 를 때고, class 이름을 Main으로 변경하면 된다.

---

개인 공부 기록용 블로그입니다.
틀리거나 오류가 있을 경우 제보해주시면 감사하겠습니다.😁