<BOJ>1926번: 그림

문제

1926번: 그림

접근

• 전형적인 bfs를 활용한 거리측정+개수세기 문제이다.
• 조건에 맞게 bfs를 구현하는게 가장 메인이다.
• N x M 크기의 그래프를 두고 그림의 정보(0: 색칠 x, 1: 색칠 o)를 바탕으로 탐색하자.

내 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int[][] graph = new int[501][501];
    static boolean[][] visited = new boolean[501][501];
    static int[] dx = {0, 0, -1, 1}; // 상,하,좌,우
    static int[] dy = {1, -1, 0, 0};
    static Queue<Node> queue = new LinkedList<>();
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine()," ");
            for (int j = 0; j < m; j++) {
                graph[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int count = 0;
        int maxSize = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (graph[i][j] == 0 || visited[i][j]) continue;
                count++;
                visited[i][j] = true;
                queue.add(new Node(i, j));
                int area = 0;
                while (!queue.isEmpty()) {
                    area++;
                    Node cur = queue.poll();
                    for (int dir = 0; dir < 4; dir++) {
                        int x = cur.getX() + dx[dir];
                        int y = cur.getY() + dy[dir];
                        if (x < 0 || x >= n || y < 0 || y >= m) continue;
                        if (graph[x][y] != 1 || visited[x][y]) continue;
                        visited[x][y] = true;
                        queue.add(new Node(x, y));
                    }
                }
                maxSize = Math.max(maxSize, area);
            }
        }
        System.out.println(count);
        System.out.println(maxSize);
    }

    static class Node {
        private int x;
        private int y;
        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
        public int getX() {
            return x;
        }
        public int getY() {
            return y;
        }
    }
}

• bfs를 알고 있다면, 쉽게 풀 수 있는 문제이다.
• 색칠이 된 부분이 어딘지 차례대로 탐색하며 그림의 크기를 센다.
• 상,하,좌,우 4방향을 움직이며 그래프 내의 모든 위치에서 bfs를 돌려야 그림의 개수를 알 수 있으니 미로 탐색과 비슷하게 방향설정을 해두자.
• 범위를 벗어나며 탐색을 하게 되는지, 이미 방문한 위치인지, 색칠이 안된 위치인지 if문으로 적절하게 제어하자.

// 후기...
1260번: DFS와 BFS 문제는 단순 구현 문제인데, 예전에 이 문제 푼 이후로 그래프 탐색을 활용하는 문제를 풀어보질 않은데다, 자다가 누가 툭 건드려서 bfs를 어떻게 구현하는지 물어보면 바로 투두두둑 짤 수 있을 정도로 기억하고 있질 않아서 그런지 오늘 하루 bfs를 일일이 생각하며 구현하느라 조금 애먹었다...

이거 때문에 bfs 뼈대 자체는 제대로 머릿속에 들어온 것 같다.

이래서 PS는 왠만하면 유형별로 매일 조금씩 풀어야 하나 싶다...