잡담: 중간고사 이후, 19학번 동기들과 코테 스터디를 하기로 했다.
스터디를 만든 형이 개념적인 부분을 설명해주고 그 형이 고른 문제들을 일주일에 최소 3문제씩 풀기로 했다.

실버1 난이도의 그래프 탐색 문제이다.

기본적인 BFS문제인데 한창 BFS를 안풀다가 오랜만에 푸니 약간 시간도 걸리고 헷갈렸다.

하나의 칸을 좌표를 저장하기 위해 Point 클래스를 만들었다.

시행착오

package BOJ;

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

public class sol1926 {

    static int[][] map;
    static boolean[][] visited;
    static int n;
    static int m;
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};
    static int maxSize;
    static int count;


    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());

        map = new int[n][m];
        visited = new boolean[n][m];


        maxSize = 0;

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


        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    bfs(i, j);
                    count++;
                }
            }
        }

        System.out.println(count);
        System.out.println(maxSize);

    }

    public static void bfs(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.add(new Point(x, y));

        int size = 0;

        while (!q.isEmpty()) {
            Point curr = q.poll();
            visited[curr.x][curr.y] = true;
            size++;
            for (int i = 0; i < 4; i++) {
                int newX = curr.x + dx[i];
                int newY = curr.y + dy[i];

                if ((newX >= 0 && newX < n) && (newY >= 0 && newY < m)) {
                    if (map[newX][newY] == 1 && !visited[newX][newY]) {
                        //visited[newX][newY] = true;
                        q.add(new Point(newX, newY));
                    }
                }
            }
        }
        maxSize = Math.max(size, maxSize);
    }

    public static class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

처음 시도한 풀이는 위 코드에서 주석부분이 없었다. 그랬더니
이런식으로 그림의 개수는 맞는데 최대 사이즈가 이상했다.

확인해보니 bfs로 상하좌우를 돌며 1인 부분을 방문처리를 안해주니 다음에 while문을 돌면서 큐에 중복해서 들어가고 있었던 것이었다.
주석부분을 추가하고 돌려보니 정답이 출력되었다.

기본적인 BFS 문제인데 시간이 너무 오래걸렸다. BFS 코드를 더 체화해서 빠르게 풀 수 있도록 해야겠다.