[백준]1012-유기농 배추 문제 풀이(Java,자바)

https://www.acmicpc.net/problem/1012

 

들어가며

처음 문제를 봤을 때, 문제를 잘못 읽어서 지렁이가 오직 한 칸만 갈 수 있는지 알아서 쓸데없이 어렵게 풀었다.

근데 다시 보니 그냥 연결요소 찾는 문제이다.

 

코드

package solved.ac.class3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 백준1012_유기농배추 {
    static int[][] dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    static boolean[][] visited;
    static int[][] arr;
    static int n,m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            ArrayList<Position> starts = new ArrayList<>();
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());

            arr = 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());
                arr[y][x] = 1;
                starts.add(new Position(y, x));
            }
            int result = 0;
            for (var start : starts) {
                if (!visited[start.y][start.x]){
                    bfs(start.x, start.y);
                    result++;
                }
            }
            System.out.println(result);
        }
    }
    static void bfs(int startX, int startY) {
        Queue<Position> queue = new ArrayDeque<>();

        queue.add(new Position(startY, startX));
        visited[startY][startX] = true;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int s = 0; s < size; s++) {
                Position position = queue.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = position.x + dir[i][0];
                    int ny = position.y + dir[i][1];
                    if (isValidMove(nx, ny)) {
                        queue.add(new Position(ny, nx));
                        visited[ny][nx] = true;
                    }
                }
            }
        }
    }

    private static boolean isValidMove( int startX, int startY) {
        if (startX < 0 || startY < 0 || startX >= m || startY >= n
                || visited[startY][startX] || arr[startY][startX] != 1) {
            return false;
        }
        return true;
    }


    static class Position {
        int y;
        int x;

        public Position(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

}

 

풀이

bfs를 통해서 지나간 곳 위치를 기록한다.

한번 bfs를 돌 때마다 개수를 기록하면 그게 곧 지렁이 마리 수가 된다.

여기서 빠르게 시작점을 찾기 위해, 1인 지점을 미리 starts라는 변수를 통해 저장한다.

그러면 모든 배열을 다 돌지 않고도 빠르게 처리할 수 있다.