[백준/JAVA] 1012 유기농 배추

유기농 배추

백준 1012번 바이러스 문제 링크

풀이

• 재귀형 DFS 알고리즘 사용했다.
• 시작은 0,0 에서 시작하고, 일반 배열과 같이 선형 탐색을 진행한다.
• 하지만 그 좌표값이 1인 경우에는 count값을 1 증가시킨다.
• 현 위치를 "0" 값으로 바꾼다.
• 현 위치를 기준으로 동서남북 사방으로 재귀함수를 통해 반복진행한다.
• 더 이상 재귀함수가 진행되지 않을 경우, 다른 "1" 값을 찾는다.
• 반복

---

제출 코드

import java.io.*;
import java.util.*;
import java.lang.*;

class Main {
    static int[][] arr;
    static int M, N, K;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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());
            arr = new int[N][M];

            K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                arr[b][a] = 1;
            }

            //임시 맵 출력
            bw.newLine();
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    bw.write(arr[j][k] + " ");
                }
                bw.flush();
                bw.newLine();
            }
            bw.newLine();
            // 여기까지

            int result = 0;
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (dfs(j, k)) {
                        result++;
                    }
                }
            }
            sb.append(result).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
    }

    static boolean dfs(int x, int y) {
        if (-1 >= x || x >= N || -1 >= y || y >= M) {
            return false;
        }
        if (arr[x][y] == 1) {
            arr[x][y] = 0;
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false;
    }
}

---

후기

뭔가 바이러스가 배추에 독을 풀려고 찾으러다니고, 한번 감염된 배추는 본인포함 근처를 다 "1" -> "0"으로 바꾸고
한번 "1"을 찾았을 때 count를 증가시킨다. 라고 생각하니 금방 이해했는데 중간에 막혔다...
알고보니 이유가 이번 문제에서 M과 N을 반대로 줘서 좀 고생좀 했다.