[백준]1012 유기농 배추(2)

bfs로 풀어본 유기농 배추 2탄 ..

package baekjoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main_1012 {
    static int M, N, K;
    static int count;

    static boolean[][] dfs;
    static boolean[][] bfs;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.valueOf(br.readLine());
        for (int i = 0; i < testCase; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.valueOf(st.nextToken());        // 배추밭 가로줄
            N = Integer.valueOf(st.nextToken());        // 배추밭 세로줄
            K = Integer.valueOf(st.nextToken());        // 배추가 심어진 갯수

            dfs = new boolean[M + 1][N + 1];            // 배추가 심어진 곳을 알기위한 배열
            bfs = new boolean[M + 1][N + 1];            // 배추가 심어진 곳을 알기위한 배열
            visit = new boolean[M + 1][N + 1];          // 카운트 체크를 위한 배열

            for (int j = 0; j < K; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
                int x = Integer.valueOf(st2.nextToken());
                int y = Integer.valueOf(st2.nextToken());
                dfs[x][y] = true;
                bfs[x][y] = true;
            }
            count = 0;
            for (int a = 0; a < M; a++) {
                for (int b = 0; b < N; b++) {
                    /*
                    if(dfs[a][b]) {
                        dfs(a, b, true);
                    }

                     */
                    if(bfs[a][b]) {
                        bfs(a, b);
                    }
                }
            }
            q.offer(count);
        }
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();

        if(visit[x][y]) {
            return;
        } else {
            count++;
            q.offer(new int[]{x, y});
            visit[x][y] = true;
        }

        while (!q.isEmpty()) {
        	int[] position = q.poll();
            int dx = position[0];
            int dy = position[1];
            visit[dx][dy] = true;

            boolean chk = false;
            // 호출 된 위치와 인접한 위치 찾기
            if (dx - 1 > -1 && bfs[dx - 1][dy] && !visit[dx-1][dy]) {
                // 상
                q.offer(new int[]{dx - 1, dy});
                chk = true;
            }
            if (dx + 1 < M && bfs[dx + 1][dy] && !visit[dx+1][dy]) {
                // 하
                q.offer(new int[]{dx + 1, dy});
                chk = true;
            }
            if (dy - 1 > -1 && bfs[dx][dy - 1] && !visit[dx][dy-1]) {
                // 좌
                q.offer(new int[]{dx, dy - 1});
                chk = true;
            }
            if (dy + 1 < N && bfs[dx][dy + 1] && !visit[dx][dy+1]) {
                // 우
                q.offer(new int[]{dx, dy + 1});
                chk = true;
            }
            if(!chk) {
                return;
            }
        }
    }
}

테스트 케이스 결과값도 다 잘나오길래 맞췄다! 싶었는데

두둥.. 메모리 초과!

수정한 소스 🙋‍♀️

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int M, N, K;
    static int count;

    static boolean[][] bfs;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        Queue<Integer> q = new LinkedList<>();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.valueOf(br.readLine());
        for (int i = 0; i < testCase; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.valueOf(st.nextToken());        // 배추밭 가로줄
            N = Integer.valueOf(st.nextToken());        // 배추밭 세로줄
            K = Integer.valueOf(st.nextToken());        // 배추가 심어진 갯수

            bfs = new boolean[M + 1][N + 1];            // 배추가 심어진 곳을 알기위한 배열
            visit = new boolean[M + 1][N + 1];          // 카운트 체크를 위한 배열

            for (int j = 0; j < K; j++) {
                StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
                int x = Integer.valueOf(st2.nextToken());
                int y = Integer.valueOf(st2.nextToken());
                bfs[x][y] = true;
            }
            count = 0;
            for (int a = 0; a < M; a++) {
                for (int b = 0; b < N; b++) {
                    /*
                    if(dfs[a][b]) {
                        dfs(a, b, true);
                    }

                     */
                    if(bfs[a][b]) {
                        bfs(a, b);
                    }
                }
            }
            q.offer(count);
        }
        while (!q.isEmpty()) {
            System.out.println(q.poll());
        }
    }
    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();

        if(visit[x][y]) {
            return;
        } else {
            count++;
            q.offer(new int[]{x, y});
            visit[x][y] = true;
        }

        while (!q.isEmpty()) {

            int[] position = q.poll();
            int dx = position[0];
            int dy = position[1];

            if((dx+1) > M || (dy+1) >N) {
                break;
            }
            // 호출 된 위치와 인접한 위치 찾기
            if (dx - 1 > -1 && bfs[dx - 1][dy] && !visit[dx-1][dy]) {
                // 상
                q.offer(new int[]{dx - 1, dy});
                visit[dx-1][dy] = true;
            }
            if (dx + 1 < M && bfs[dx + 1][dy] && !visit[dx+1][dy]) {
                // 하
                q.offer(new int[]{dx + 1, dy});
                visit[dx+1][dy] = true;
            }
            if (dy - 1 > -1 && bfs[dx][dy - 1] && !visit[dx][dy-1]) {
                // 좌
                q.offer(new int[]{dx, dy - 1});
                visit[dx][dy-1] = true;
            }
            if (dy + 1 < N && bfs[dx][dy + 1] && !visit[dx][dy+1]) {
                // 우
                q.offer(new int[]{dx, dy + 1});
                visit[dx][dy+1] = true;
            }
        }
    }
}

🙋‍♀️ 풀이
dfs와 엄청나게 비슷한 걸 알 수 있다! 위치가 동떨어져있을 땐 새로 시작점을 불러줘야 한다고 생각해서 for안에서 배추가 있는 위치의 bfs 함수를 호출했다.
호출 시점에 카운트를 올려주고 인접한 위치여서 큐에 추가되는 건 카운팅에서 제외해줬다.
인접 배추를 찾는 과정은 dfs와 마찬가지로 상하좌우 요리조리 살펴서 찾았고 큐에 들어가기 전에 이미 방문완료 처리를 하지 않으면 메모리 초과가 일어난다.
나는 position 변수에서 값을 빼고나서야 visit[dx][dy] = true 처리를 해줬는데 이렇게 되면 다른 배추의 상하좌우를 살피면서 중복으로 값이 들어가기 때문에 메모리 초과가 난다고 한다. 그래서 큐에 이미 값이 들어가서 처리되려고 할때 완료 처리를 하는게 아니라 큐에 넣는 시점에 visit true로 바꿔줘야한다.
배추밭을 넘으면 break 걸어주고 ~ 카운팅을 출력해주면 완료!

히히 프린트문 안빼서 출력 초과난 거 빼고 성공!