[BOJ] 1012 유기농 배추

유기농배추

풀이

• 2차원 배열로 map 구현
• 2차원 배열 visited로 방문 처리
• 사방탐색 dx,dy 배열로 처리
• bfs 구현 -> Queue 사용
• dfs 구현 가능
• 1이 모여 있는 구역을 찾아서 count하는 문제.
• 토마토, 미로, 단지 등과 같은 유형
• 2중 for문으로 map 돌면서 1이고 아직 방문하지 않았으면 bfs 호출하여 인접한 배추(1)을 탐색한다.
  bfs 호출할 때마다 count를 증가시킨다.

코드

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

public class BOJ1012 {
    static int M, N;
    static int[][] map;
    static boolean[][] visited;
    static int answer;
    static int[] dx = { -1, 1, 0, 0 };
    static int[] dy = { 0, 0, -1, 1 };
    static Queue<int[]> queue = new LinkedList<>();

    public static void main(String[] args) throws Exception {

        //구역 찾기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            map = new int[N][M];
            visited = new boolean[N][M];
            answer = 0;
            for (int j = 0; j < K; j++) {
                //배추 위치 X,Y
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                map[Y][X] = 1; //배추 위치 1로 표시
            }

            for (int j = 0; j < N; j++) {
                for (int v = 0; v < M; v++) {
                    if (map[j][v] == 1 && !visited[j][v]) {
                        // bfs(j, v);
                        dfs(j, v);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
        }
    }

    private static void dfs(int j, int v) {
        visited[j][v] = true;
        for (int i = 0; i < 4; i++) {
            int y = dy[i] + j;
            int x = dx[i] + v;
            if (y >= 0 && y < N && x >= 0 && x < M && map[y][x] == 1 && !visited[y][x]) {
                dfs(y, x);
            }
        }

    }
    
    private static void bfs(int j, int v) {
        visited[j][v] = true;
        queue.offer(new int[] { j, v });

        while (!queue.isEmpty()) {
            int[] tmp = queue.poll();
            int y = tmp[0];
            int x = tmp[1];
            for (int i = 0; i < 4; i++) {
                int tx = x + dx[i];
                int ty = y + dy[i];
                if (tx >= 0 && tx < M && ty >= 0 && ty < N) {
                    if (map[ty][tx] == 1 && !visited[ty][tx]) {
                        visited[ty][tx] = true;
                        queue.offer(new int[] { ty, tx });
                    }
                }
            }
        }
    }

}