[코테] 백준 1012 유기농 배추: DFS Java

DFS, BFS 둘 다 풀 수 있는 문제다.

 

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

 

백준은 항상 입력 부분과 로직 부분을 나눠서 생각한다. ...

 

1) 입력 부분

public static void main(String[] args) throws NumberFormatException, IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int tc = Integer.parseInt(br.readLine()); // 테스트 케이스의 갯수

    for (int i = 0; i < tc; i++) {
        count = 0;
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken()); // 배추밭 가로 길이
        N = Integer.parseInt(st.nextToken()); // 배추밭 세로 길이
        field = new int[M][N];
        visit = new boolean[M][N];

        cabbageCount = Integer.parseInt(st.nextToken()); // 배추 갯수
        for (int j = 0; j < cabbageCount; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken()); // 배추 심어져있는 좌표 x
            int y = Integer.parseInt(st.nextToken()); // 배추 심어져있는 좌표 y
            field[x][y] = 1; // 배추 심어져있는 곳 표시
        }
    }
}

요구사항에 맞는 입력을 받는다.

 

 

2) 로직 부분

static void dfs(int x, int y) {
    visit[x][y] = true; // 방문 처리

    for (int i = 0; i < 4; i++) {
        // x, y 좌표 기준 4방면 탐방
        int cx = x + dx[i];
        int cy = y + dy[i];

        // 해당 좌표가 올바른 좌표인지 확인 (양배추 필드에 들어가는 좌표인지)
        if (cx >= 0 && cy >= 0 && cx < M && cy < N) {
            // 해당 좌표에 방문한 적 있다면 dfs 함수 끝
            // 해당 좌표에 방문한 적 없고, 양배추가 있는 좌표라면 재귀 호출
            if (!visit[cx][cy] && field[cx][cy] == 1) {
                dfs(cx, cy);
            }
        }
    }
}

문제는 배추에 풀어놓을 지렁이의 수를 구하는 것이다.

배추는 인접되어있으면 하나의 지렁이만 필요하기 때문에 

배추의 묶음이 총 몇개인지 구하면 된다.

 

처음 dfs 함수를 호출할 때 count를 ++ 해준다. 배추가 있는 칸에서 dfs를 호출한다.

그리고 dfs함수에서는 방문 처리를 해주고,

배추가 있는 칸 기준 상, 하, 좌, 우를 탐방한다.

올바른 좌표인데다가 양배추가 있다면 dfs를 한 번 더 호출한다. 각 방향대로 쭉 양배추가 없을 때까지 방문 처리를 하는 것이다.

 

상, 하, 좌, 우 양배추가 있는 곳에 방문 처리가 끝났다면 dfs 함수를 끝낸다.

 

최종 코드

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

public class baekjoon_1012 {
    static int M, N;
    static int cabbageCount;
    static int[][] field;
    static boolean[][] visit;
    static int count;
    static int[] dx = { 0, -1, 0, 1 };
    static int[] dy = { 1, 0, -1, 0 };

    public static void main(String[] args) throws NumberFormatException, IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine()); // 테스트 케이스의 갯수

        for (int i = 0; i < tc; i++) {
            count = 0;
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            M = Integer.parseInt(st.nextToken()); // 배추밭 가로 길이
            N = Integer.parseInt(st.nextToken()); // 배추밭 세로 길이
            field = new int[M][N];
            visit = new boolean[M][N];

            cabbageCount = Integer.parseInt(st.nextToken()); // 배추 갯수
            for (int j = 0; j < cabbageCount; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken()); // 배추 심어져있는 좌표 x
                int y = Integer.parseInt(st.nextToken()); // 배추 심어져있는 좌표 y
                field[x][y] = 1; // 배추 심어져있는 곳 표시
            }

            for (int x = 0; x < M; x++) { // 가로 길이만큼
                for (int y = 0; y < N; y++) { // 세로 길이 만큼
                    if (field[x][y] == 1 && !visit[x][y]) { // 양배추가 있고, 방문을 안한 곳이라면 dfs 함수
                        dfs(x, y);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

    }

    static void dfs(int x, int y) {
        visit[x][y] = true; // 방문 처리

        for (int i = 0; i < 4; i++) {
            // x, y 좌표 기준 4방면 탐방
            int cx = x + dx[i];
            int cy = y + dy[i];

            // 해당 좌표가 올바른 좌표인지 확인 (양배추 필드에 들어가는 좌표인지)
            if (cx >= 0 && cy >= 0 && cx < M && cy < N) {
                // 해당 좌표에 방문한 적 있다면 dfs 함수 끝
                // 해당 좌표에 방문한 적 없고, 양배추가 있는 좌표라면 재귀 호출
                if (!visit[cx][cy] && field[cx][cy] == 1) {
                    dfs(cx, cy);
                }
            }

        }

    }
}