[백준 #1926] 그림

백준 #1926 그림

백준 #1926

---

문제 설명👩‍🏫

어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로로 연결된 것은 연결이 된 것이고 대각선으로 연결이 된 것은 떨어진 그림이다. 그림의 넓이란 그림에 포함된 1의 개수이다.

입출력 예

입력
6 5
1 1 0 1 1
0 1 1 0 0
0 0 0 0 0
1 0 1 1 1
0 0 1 1 1
0 0 1 1 1

출력
4
9

---

내 코드💻

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

public class Main {
    static int[][] visited;
    static int[][] list;
    static int []dicX ={0,0,1,-1};
    static int []dicY ={1,-1,0,0};
    static int h,w,nowX, nowY;
    static int max = 0;
    static int sum = 0;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringTokenizer st = new StringTokenizer(str," ");
        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        list = new int[h][w];
        visited = new int[h][w];
        for(int i=0;i<h;i++){
            str = br.readLine();
            st = new StringTokenizer(str," ");
            for(int j=0;j<w;j++){
                list[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int count = 0;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                if(visited[i][j] == 0 && list[i][j] == 1) {
                    count++;
                    sum = 0;
                    dfs(i, j);
                    if(max < sum) max = sum;
                }
            }
        }
        System.out.println(count);
        System.out.println(max);


    }
    static void dfs(int  i, int j){
        sum++;
        visited[i][j] = 1;

        for(int n=0;n<dicX.length;n++){
            nowX = i + dicX[n];
            nowY = j + dicY[n];
            if (checking(nowX,nowY)&& visited[nowX][nowY] == 0 && list[nowX][nowY] == 1) {
                dfs(nowX, nowY);
            }
        }
    }

    static boolean checking(int x, int y){
        return (x >=0 && x < h && y >=0 && y < w);
    }
}

---

설명💡

방향을 나타내는 dicX, dicY를 사용해서, 오른쪽, 왼쪽, 위쪽, 아래쪽으로 한칸 씩 움직이도록 한다. DFS를 공부하고 나서 전체적인 코드는 써내려갈 수 있었다.

---

조금 헤맸던 부분은 출력할 count와 max를 어떻게 구해야할까였다. count는 main함수에서 dfs함수가 실행되기 전에 추가하면, 전체 그림의 개수가 나온다.
max는 sum 변수를 추가로 사용하여, main의 dfs 함수마다 sum을 증가시켜 그림의 넓이를 구하고, 그 넓이가 기존의 max보다 크다면 변경시켜, 전체 도화지의 max를 구할 수 있었다.

---

느낀 점 및 궁금한 점🍀

DFS, BFS는 아무리 봐도 보면 볼수록 헷갈린다.. 볼땐 이해가 되는데 혼자하려면 또 어렵고.. 더 공부해야할 부분이다..
count와 max와 sum을 변화시키는 부분을 어디에 넣어야할지 헷갈렸다..😭