[백준 1012/자바] 유기농 배추

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

1012번: 유기농 배추

 

---

 

진짜 푸는 데 오래 걸렸음...

나한테 생소한 개념들이라 이번에 이거 찾아보면서 공부 많이 한 것 같다

더해야됨

아래 참고한 블로그에 설명이 너무 잘 되어있어서 도움 많이 받았다

 

✨ 참고
https://lotuus.tistory.com/98

---

 

풀이

인접한 배추를 찾아 탐색해야 하므로 DFS 사용

한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이므로 dx, dy를 사용

배추의 경우 0, 1로 존재 여부를 판단하므로 2차원 boolean 배열 사용

 

1. 방문하지 않았던 좌표인데 배추도 있는 경우 지렁이 수를 +1 한 후 인근 배추 탐색(dfs 실행)

2. 상하좌우로 배추를 탐색하다가 배추가 없는 부분이나 이미 방문한 좌표를 만나면 재귀 함수(dfs) 끝냄

 

코드

• dx, dy

static int[] dirX = {-1, +1, 0, 0};
static int[] dirY = {0, 0, -1, +1};

 

• dfs()

// 배추밭을 돌며 방문 처리하는 함수
static void dfs(int startX, int startY) {
    // 방문한 배추거나 배추가 없는 부분이면 재귀 끝냄
    if (isVisited[startY][startX] || !farm[startY][startX]) {
        return;
    }

    // 방문 처리
    isVisited[startY][startX] = true;

    // 현재 배추의 상하좌우 네 방향 탐색
    for (int i = 0; i < 4; i++) {
        // 새로 탐색할 위치
        int x = startX + dirX[i];
        int y = startY + dirY[i];

        // 배열 범위를 벗어나면 탐색하지 않음
        if (x < 0 || y < 0 || x >= M || y >= N) {
            continue;
        }

        dfs(x, y);
    }
}

 

• main

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    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());

        farm = new boolean[N][M];
        isVisited = 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());

            farm[Y][X] = true;  // 배추가 있는 부분
        }

        int count = 0;
        // 밭 전체를 돌며 배추가 있는지 확인
        // 배추가 있고, 방문하지 않았던 배추면 count + 1
        for (int j = 0; j < N; j++) {
            for (int k = 0; k < M; k++) {
                if (farm[j][k] && !isVisited[j][k]) {
                    count++;
                    dfs(k, j);
                }
            }
        }

        sb.append(count).append('\n');
    }

    System.out.println(sb);
}

 

• 전체

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

public class Main {
    static boolean[][] farm;
    static boolean[][] isVisited;
    static int[] dirX = {-1, +1, 0, 0};
    static int[] dirY = {0, 0, -1, +1};
    static int N, M;

    static void dfs(int startX, int startY) {
        // 방문한 배추거나 배추가 없는 부분이면 재귀 끝냄
        if (isVisited[startY][startX] || !farm[startY][startX]) {
            return;
        }

        // 방문 처리
        isVisited[startY][startX] = true;

        // 현재 배추의 상하좌우 네 방향 탐색
        for (int i = 0; i < 4; i++) {
            // 새로 탐색할 위치
            int x = startX + dirX[i];
            int y = startY + dirY[i];

            // 배열 범위를 벗어나면 탐색하지 않음
            if (x < 0 || y < 0 || x >= M || y >= N) {
                continue;
            }

            dfs(x, y);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        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());

            farm = new boolean[N][M];
            isVisited = 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());

                farm[Y][X] = true;  // 배추가 있는 부분
            }

            int count = 0;
            // 밭 전체를 돌며 배추가 있는지 확인
            // 배추가 있고, 방문하지 않았던 배추면 count + 1
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (farm[j][k] && !isVisited[j][k]) {
                        count++;
                        dfs(k, j);
                    }
                }
            }

            sb.append(count).append('\n');
        }

        System.out.println(sb);
    }
}