[백준] 1012번 : 유기농 배추

유기농 배추

---

풀이 방법

이 문제는 백준을 접한지 얼마 안됐을 때, 무작정 풀려고 했다가 실패한 문제였다.
이제와서 보니 그래프 탐색 문제였고, 좌표 또한 이용해야 했다.
시뮬레이션 문제, 그래프 탐색 문제도 접해봤기에 좀더 쉽게 접근할 수 있던 문제였다.

최종 풀이 방법은
DFS를 이용했고, 좌표를 mx, my로 미리 옮겨서 옮길 수 있는지, 방문하지 않았는지, 배추흰지렁이가 존재하는지 체크해 DFS 탐색을 진행하면 되는 문제였다.

느낀 점

아직까진 문제를 보면 어떤 알고리즘으로 풀어야 하는지 감이 잘 잡히지 않는다..
아직 많은 문제를 풀어보지 못해 그런 것 같다. 꾸준히 열심히 하는 것을 목표로!

---

소스 코드

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

public class Main {
    static boolean[][] visited;
    static int[][] ground;
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};

    static int m, n;

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

            init(k); //초기화

            for(int j=0;j<k;j++){
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                ground[y][x] = 1;
            }

            int count=0;
            for(int j=0;j<n;j++){
                for(int l=0;l<m;l++){
                    if(ground[j][l]==1 && !visited[j][l]){ //방문하지 않았으며, 지렁이가 존재한다면 탐색
                        count++;
                        dfs(j,l);
                    }
                }
            }
            System.out.println(count);
        }


    }
    private static void init(int k) {
        ground = new int[n][m];
        visited = new boolean[n][m];
    }
    private static void dfs(int x, int y) {
        visited[x][y] = true; //방문 처리

        for(int i=0;i<4;i++){
            //미리 옮겨봄
            int mx = x + dx[i];
            int my = y + dy[i];

            //땅 내에 존재하고, 방문하지 않았으며, 지렁이가 존재한다면
            if(mx<n && mx>=0 && my<m && my>=0 && !visited[mx][my] && ground[mx][my]==1)
                dfs(mx,my);
        }

    }
}