[BOJ - JAVA] 1926 - 그림 (DFS)

# 문제

# 주소

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

1926번: 그림

# 문제 해설 및 코드 리뷰

import java.awt.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[][] arr;
    static boolean[][] visit;
    static int[] dx = {1, 0, 0, -1};
    static int[] dy = {0, 1, -1, 0};
    static int count = 0;
    static int S = 0;
    static int s=0;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        m = scan.nextInt();

        arr = new int[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                arr[i][j] = scan.nextInt();
            }
        }
        visit = new boolean[n][m];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(!visit[i][j] && arr[i][j] == 1){
                    S = Math.max(S,dfs(i,j));
                    count++;
                }
            }
        }
        System.out.println(count);
        System.out.println(S);
    }
    public static int dfs(int x, int y){
        visit[x][y] = true;
        s=1;
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x,y));
        while (!queue.isEmpty()) {
            Point now = queue.poll();
            for(int i = 0; i < 4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if(visit[nx][ny])
                    continue;
                if(arr[nx][ny] == 1) {
                    queue.offer(new Point(nx,ny));
                    visit[nx][ny] = true;
                    s++;
                }
            }
        }
        return s;
    }
}

포스팅이 많이 늦었습니다..

스프링부트 공부하는데 MariaDB 재설치를 하는 과정에서 자꾸만 설치가 중단되길래 별에별 짓을 다했습니다.

안될리가 없는데 MongoDB도 지우고 MySQL도 지우고 윈도우 초기화도 해보고 MariaDB관련된 파일 전부 다 지우고 C++ 재배포 재설치도 해보고 껐다 켜보기도 하고 MariaDB 다른 버전들 싹 다 깔아보기도 했는데 역시 설치가 안되더라고요.

그렇게 이틀을 낭비하면서(솔직히 문법이나 에러가 뜨면 구글에 찾아보면 되는데 MariaDB가 설치 중단되면서 에러 로그 하나 안띄워주니까 어안이 벙벙하더라고요) 아무것도 못했습니다 ㅋㅋㅋ.

그래서 그냥 포맷하고 (하.. 아까운 내 논문 자료 + 공부했던거..) 구글드라이브에 옮기긴 했습니다만 용량 부족으로 나머지는 그냥 슬프게도 지웠습니다.

포맷하고 나니까 설치가 잘되네요.

결국 뭐가 원인인지는 저도 모릅니다. 

구글에 10Page넘게 뒤져봐도 저같은 사람은 없어보이네요.

그냥 윈도우11이 문제인 것 같습니다 ㅎㅎ...

어쨌든 각설하고 이틀전에 푼 문젠데 경황이 없어서 포스팅을 못하다가 이제서야 올립니다.

난이도 자체는 실버1난이도 답게 어렵지 않았습니다.

 

arr = new int[n][m];
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        arr[i][j] = scan.nextInt();
    }
}
visit = new boolean[n][m];
for(int i = 0; i < n; i++){
    for(int j = 0; j < m; j++){
        if(!visit[i][j] && arr[i][j] == 1){
            S = Math.max(S,dfs(i,j));
            count++;
        }
    }
}

일단 arr를 선언하고 입력값을 받아옵니다.

그리고 visit이 false이고 arr가 1인 지점을 방문하여 인접해 있는 그림의 영역을 찾아냅니다.

예제에서는 4개의 그림이 나오는데, 각 연결된 점을 모두 잇는다고 할 떄 dfs문은 총 4번 실행되므로 count값도 4번 ++됩니다. 

그래서 이 count를 출력하시면 첫 번째 그림의 개수를 clear하게 될 것입니다.

하지만 두 번째 문에서 많이 막힐거에요. (사실 어렵진 않지만 첫 번째보단 어렵습니다)

백준에서 bfs문제 풀다보면 그림 개수 구하는건 꽤 많이 나옵니다.

그렇지만 두 번째는 첫 번째 구하는 것보다 덜나오기 때문인데요. 그래도 쉬우니까 같이 봅시다.

public static int dfs(int x, int y){
    visit[x][y] = true;
    s=1;
    Queue<Point> queue = new LinkedList<>();
    queue.offer(new Point(x,y));
    while (!queue.isEmpty()) {
        Point now = queue.poll();
        for(int i = 0; i < 4; i++){
            int nx = now.x + dx[i];
            int ny = now.y + dy[i];
            if(nx < 0 || ny < 0 || nx >= n || ny >= m)
                continue;
            if(visit[nx][ny])
                continue;
            if(arr[nx][ny] == 1) {
                queue.offer(new Point(nx,ny));
                visit[nx][ny] = true;
                s++;
            }
        }
    }
    return s;

Queue를 이용하여 각 점을 queue에 담고 인접해 있는 점을 계속해서 방문합니다.

단, 인덱스가 0보다 작거나 n과 m을 넘겨서는 안되며 방문한 지점도 continue해주어야 합니다.

그리고 만약 arr지점이 1인 곳을 찾았을 때 queue에 담고 s의 값을 계속 증가시킵니다.

이 s의 값이 그림의 영역이며 방문하는 지점마다 s가 늘어나므로 방문한 지점이 9이면 영역의 넓이 또한 9가 됩니다.

따라서 이 s를 return함으로써 S에 담아, 계속해서 다음 dfs문과 비교해주면서 가장 큰 S를 출력하면 그것이 정답입니다.

어렵지 않죠?

진짜 어려운거 하나도 없습니다.

우선 탐색 문제의 가장 정석문제같네요.

감사합니다.