[자바]백준 1316번 그룹 단어 체커 [그래프 탐색][엄탱]

안녕하세요. 개발자 엄탱입니다.
이 글은 알고리즘을 공부하면서 공부 기록용입니다.
그래서 설명마다 일기용으로 편하게 작성하여 반말 형식으로 작성하려고 합니다.
그리고 보시다가 더 좋은 방법이나 잘 못 알고 있는 내용이 있다면 알려주시면 정말 감사하겠습니다.
좋은 하루 되세요 :)

문제 링크

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

1012번: 유기농 배추

 

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추 흰 지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해 있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데 군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해 있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

문제 설명에 필요한 예시

문제 설명

위의 사진을 보면 0과 1이 있는데 1이 배추가 심어져 있는 위치이며 지렁이가 배추가 있으면 이동이 가능하여 배추가 이어져 있으면 같은 구간으로 쳐서 지렁이 한 마리가 필요하다.

그래서 위에 사진은 총 5구간이 있고 지렁이 5마리가 필요하다.

해설

해당 문제는 생각보다는 쉽다. 아래 방식대로 하면 된다.

1. 1과 0을 갖고 있는 배열을 처음부터 끝까지 완전탐색을 한다.
2. 1을 만나면 지렁이 마리수를 1 증가시키고 dfs를 하든 bfs를 하든 어떤 방식으로든 인접한 배추를 0으로 체크해준다.

위와 같은 방식으로만 하면 탐색이 끝나고 나면 답이 구해져 있을 것이다.

여기서, 2번만 설명이 필요할 것 같다.

 

완전 탐색을 하면서 1을 발견하면 새로운 배추 구간이라고 인지하는 것이기 때문에 마릿수를 체크해 준 배추 구간의 배추들은 0으로 변경해 줘서 다음 탐색에서 그냥 지나 칠 수 있게 해 주기 위함이다.

코드

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

public class Main {
    static int M = 0;
    static int N = 0;
    static int K = 0;
    static int[][] arr;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int T = Integer.parseInt(br.readLine());

        for (int i = 0; i < T; i++) {
            System.out.println(testCase());
        }

        br.close();
    }

    public static int testCase() throws Exception {
        int result = 0;

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        M = Integer.parseInt(st.nextToken()); // 배추 가로 길이
        N = Integer.parseInt(st.nextToken()); // 배추 세로 길이
        K = Integer.parseInt(st.nextToken()); // 배추가 심어져 있는 위치의 개수

        arr = new int[M][N];

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine(), " ");

            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());

            arr[m][n] = 1;
        }

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1) {
                    search(i, j);
                    result++;
                }
            }
        }

        return result;
    }

    public static void search(int x, int y) {
        if (arr[x][y] == 0) {
            return;
        }

        arr[x][y] = 0;

        if (x - 1 >= 0) {
            search(x - 1, y);
        }

        if (y - 1 >= 0) {
            search(x, y - 1);
        }

        if (x + 1 < M) {
            search(x + 1, y);
        }

        if (y + 1 < N) {
            search(x, y + 1);
        }
    }
}

코드 설명

코드는 길어 보이지만 어렵지 않으니 천천히 읽어보면 금방 알 수 있을 것이다.

 

이 문제는 시간초과가 날 것 같다고 생각하고 풀었는데 내 생각한 방식이 한 번에 맞춰서 묘한 쾌감을 얻은 문제다..