문제 출처

단계별로 풀어보기 > 그래프와 순회 > 유기농 배추
https://www.acmicpc.net/problem/1012

문제 설명

배추흰지렁이는 배추근처에서 해충을 잡아 먹어서 배추를 보호한다.
배추흰지렁이는 인접한 다른 배추로 이동할 수 있어서, 현재 배추 상하좌우의 배추까지 보호 받을 수 있다.
테스트 케이스 T, 배추밭 가로 길이 M, 세로 길이 N, 배추 갯수 K가 주어질 때, 각 테스트 케이스에 대해 필요한 배추흰지렁이의 마리 수를 출력하라.

접근 방법

BFS를 이용하여 풀이한다.
배추가 있는 장소를 ground, 배추흰지렁이가 한 번 들린 곳을 visited라 할 때,
배추흰지렁이의 이동방향 dx, dy를 설정한다.
이 후, bfs를 진행하면 된다.

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

public class 유기농_배추 {
    public static int[][] ground;
    public static boolean[][] visited;
    public static int result;

    public static int[] dx = {-1, 1, 0, 0};
    public static int[] dy = {0, 0, -1, 1};

    public static void bfs(int x, int y, int N, int M){
        if(ground[x][y] != 1 || visited[x][y]) return;
        result++;

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y});
        visited[x][y] = true;

        while(!q.isEmpty()){
            int[] temp = q.poll();

            for(int i = 0; i < 4; i++){
                int nx = temp[0] + dx[i];
                int ny = temp[1] + dy[i];

                if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(ground[nx][ny] == 0 || visited[nx][ny]) continue;

                visited[nx][ny] = true;
                q.add(new int[]{nx,ny});
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        for(int i = 0; i < T; i++){
            result = 0;
            st = new StringTokenizer(br.readLine());
            int M = Integer.parseInt(st.nextToken());
            int N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());

            ground = new int[N][M];
            visited = new boolean[N][M];

            for(int j = 0; j < K; j++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                ground[y][x] = 1;
            }

            for(int x = 0; x < N; x++){
                for(int y = 0; y < M; y++){
                    bfs(x, y, N, M);
                }
            }
            sb.append(result).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

가로, 세로에 대한 설정을 잘 못해서 그 부분에서 조금 해맸다.

해당 코드의 시간 복잡도는 O(T x M x N x 4) = O(T x M x N)이다.

문제푼 흔적