[DFS/BFS] 백준 - 1926번: 그림 Java 풀이

[공부용이기 때문에 코드가 깔끔하지 않을 수 있습니다!]

 

1926번: 그림

 

문제의 해석은 다음과 같다.

2차원 배열에 1이 되어있는 부분은 색칠된 부분이고 동서남북으로 이루어져 있는 그림을 하나의 그림으로 보고

그 그림의 개수를 print하고, 그림들 중에 가장 많은 면적을 차지하는 그림의 1의 개수를 표현하는 것이다.

 

문제는 DFS로 방문처리해주면서 카운트와 면적을 구하면 된다.

 

코드(DFS)

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static boolean[][] map;
    static boolean[][] visit;
    static int n;
    static int m;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int count;
    static List<Integer> big;
    static int num;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine();

        map = new boolean[n][m];
        visit = new boolean[n][m];
        count = 0;
        num = 1;
        big = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            String[] s = str.split(" ");
            for (int j = 0; j < s.length; j++) {
                if (s[j].equals("1")) {
                    map[i][j] = true;
                }
            }
        }


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && map[i][j]) {
                    count++;
                    dfs(i, j);
                    big.add(num);
                    num = 1;
                }
            }
        }

        System.out.println(count);
        if (big.isEmpty()) {
            System.out.println("0");
        } else {
            System.out.println(Collections.max(big));
        }
    }

    private static void dfs(int x, int y) {
        visit[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nowX = x + dx[i];
            int nowY = y + dy[i];

            if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                if (!visit[nowX][nowY] && map[nowX][nowY]) {
                    dfs(nowX, nowY);
                    num++;
                }
            }
        }
    }
}

 

이번 코드는 좀 더럽게 짜진 것 같지만 풀었으니까 올립니다!

 

+ BFS 코드 추가

 

코드(BFS)

//BFS
import java.util.*;

public class Main {
    static boolean[][] map;
    static boolean[][] visit;
    static int n;
    static int m;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};
    static int count;
    static int max;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();
        sc.nextLine();

        map = new boolean[n][m];
        visit = new boolean[n][m];
        count = 0;
        max = 0;

        for (int i = 0; i < n; i++) {
            String str = sc.nextLine();
            String[] s = str.split(" ");
            for (int j = 0; j < s.length; j++) {
                if (s[j].equals("1")) {
                    map[i][j] = true;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && map[i][j]) {
                    count++;
                    visit[i][j] = true;
                    max = Math.max(max, bfs(i, j));
                }
            }
        }

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

    private static int bfs(int x, int y) {
        int rs = 1;
        Queue<Coordinate> q = new LinkedList<>();
        q.add(new Coordinate(x, y));

        while (!q.isEmpty()) {
            Coordinate c = q.remove();
            for (int i = 0; i < 4; i++) {
                int nowX = c.x + dx[i];
                int nowY = c.y + dy[i];

                if (nowX >= 0 && nowY >= 0 && nowX < n && nowY < m) {
                    if (!visit[nowX][nowY] && map[nowX][nowY]) {
                        rs++;
                        q.add(new Coordinate(nowX, nowY));
                        visit[nowX][nowY] = true;
                    }
                }
            }
        }

        return rs;
    }

    static class Coordinate {
        int x;
        int y;

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