[Baekjoon] 1926번 그림 (Java) 문제 풀이 [Sliver 1]

문제

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

1926번: 그림

 

어떻게 풀 것인가?

Stack을 이용한 DFS를 활용하여 문제를 풀어야한다.

DFS를 통해서 접근한 영역의 갯수와 영역의 넓이를 구한다면 아주아주 쉽게 문제를 풀 수 있다.

 

풀면서 놓쳤던점

DFS에서는 2가지의 방식으로 문제를 풀 수 있다. 바로 재귀와 Stack을 활용한 방법이다.

다만, 재귀를 통해서 문제를 푼다면 StackOverFlow가 발생한다. 이러한 부분을 처음에 놓쳐서 문제를 다시 수정해야 했다.

 

이 문제를 통해 얻어갈 것

DFS의 간단한 활용

 

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

class Coordinate {
    int x;
    int y;


    Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int m;
    static int n;

    static int[][] arr;
    static boolean[][] visit;

    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int max = 0;

    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());
        arr = new int[n][m];
        visit = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int number = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && arr[i][j] == 1) {
                    number++;
                    DFS(i, j);
                }
            }
        }

        System.out.println(number);
        System.out.println(max);
    }

    private static void DFS(int x, int y) {
        Stack<Coordinate> stack = new Stack<>();
        stack.push(new Coordinate(x, y));
        int num = 1;
        visit[x][y] = true;
        while (!stack.isEmpty()) {
            Coordinate current = stack.pop();
            int cx = current.x;
            int cy = current.y;

            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (range(nx, ny) && arr[nx][ny] == 1) {
                    if (!visit[nx][ny]) {
                        stack.push(new Coordinate(nx, ny));
                        visit[nx][ny] = true;
                        num++;
                    }
                }
            }
        }
        if (max < num) max = num;
    }

    private static boolean range(int x, int y) {
        return ((x < n) && (x >= 0)) && ((y < m) && (y >= 0));
    }

}

 

참고

X