[BAEKJOON] - 1926번 : 그림

1926번 문제 링크

참고 포스팅

• https://m.blog.naver.com/sosow0212/222734179359

📜 알고리즘 접근 방법

해당 문제는 DFS 또는 BFS로 접근이 가능한 문제입니다.

필자는 해당 문제를 DFS로 접근하였습니다.

간단하게 설명드리면, 도화지에 그림이 그려진 부분은 '1' 이라는 값이 담긴 부분이고, 그려지지 않은 부분은 '0'인 부분입니다.

우선, 도화지와 방문 표시를 할 2차원 배열 2개를 선언 및 초기화 해줍니다.

그 다음으로, 이중 for문을 돌려 그림이 그려졌는지 여부(1)와 방문 여부를 확인하여 dfs를 탐색해줍니다.

탐색이 발생했다는 것은 깊이(depth)가 한단계 깊어졌음을 의미하기 때문에 depth의 카운팅을 늘려줍니다.

탐색 시, 현재 위치의 가로 세로만 확인하면 되기 때문에 dx{1,0,-1,0},dy{0,1,0,-1}를 사용하여 값을 조회하도록 해줍니다.(가로,세로 탐색)

주의할점

가로, 세로 탐색 시 범위를 잘 확인해줘야 합니다. 잘못하면 IndexOutOfBounds Exception이 발생할 수 있기 때문에 주의해야 합니다.

c < 0 || c >= n || r < 0 || r >= m

early return

도화지에 값을 초기화 할 때, 1이 없는 경우 isZero의 초기화한 true로 인해 if문으로 0 2개를 출력 후 메인 메서드를 종료시킵니다.(성능 개선)

DFS 코드는 아래와 같습니다.

    static void dfs(int col, int row) {
        visited[col][row] = true;
        depth++;

        for (int i = 0; i < 4; i++) {
            int c = col + dy[i];
            int r = row + dx[i];

            if (c < 0 || c >= n || r < 0 || r >= m)
                continue;

            if (paper[c][r] != 0 && !visited[c][r])
                dfs(c, r);
        }
    }

위 코드의 경우, (0,0)이 바로 0 값이 나오게 될 경우, depth가 1 증가하게 되는 오류가 있습니다. 이를 방지하기 위해서 dfs 호출 시 0이 아닌 경우에만 dfs를 호출하도록 구현하였습니다.

👾 성공

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

public class Main {
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static boolean[][] visited;
    static int[][] paper;
    static int n, m;
    static int depth;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] s = br.readLine().split(" ");

        n = Integer.parseInt(s[0]); // 열

        m = Integer.parseInt(s[1]); // 행

        visited = new boolean[n][m]; // 방문 배열

        paper = new int[n][m]; // 도화지

        ArrayList<Integer> draws = new ArrayList<>();

        boolean isZero = true;

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());

                if (isZero && paper[i][j] == 1) {
                    isZero = false;
                }
            }
        }

        if (isZero) {
            System.out.println(0);
            System.out.println(0);
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (paper[i][j] != 0 && !visited[i][j]) {
                    depth = 0;
                    dfs(i, j);
                    draws.add(depth);
                }
            }
        }

        br.close();

        StringBuilder sb = new StringBuilder();

        sb.append(draws.size()).append("\n");

        int max = 0;

        for (int i = 0; i < draws.size(); i++) {
            if (max < draws.get(i))
                max = draws.get(i);
        }

        sb.append(max).append("\n");

        System.out.println(sb);
    }

    static void dfs(int col, int row) {
        visited[col][row] = true;
        depth++;

        for (int i = 0; i < 4; i++) {
            int c = col + dy[i];
            int r = row + dx[i];

            if (c < 0 || c >= n || r < 0 || r >= m)
                continue;

            if (paper[c][r] != 0 && !visited[c][r])
                dfs(c, r);
        }
    }
}