kingsubin

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

public class Main {

    static int t, m, n, k, x, y, ans;
    static int[][] graph = new int[50][50];

    public static boolean dfs(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n) {
            return false;
        }

        if (graph[x][y] == 1) {
            graph[x][y] = 0;

            dfs(x - 1, y);
            dfs(x + 1, y);
            dfs(x, y - 1);
            dfs(x, y + 1);

            return true;
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        t = Integer.parseInt(br.readLine());

        // 테스트 케이스 갯수만큼 반복
        for (int i = 0; i < t; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            m = Integer.parseInt(st.nextToken());
            n = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());

            // 배추가 심어진 곳 표시
            for (int j = 0; j < k; j++) {
                st = new StringTokenizer(br.readLine());

                x = Integer.parseInt(st.nextToken());
                y = Integer.parseInt(st.nextToken());

                graph[x][y] = 1;
            }

            for (int j = 0; j < m; j++) {
                for (int l = 0; l < n; l++) {
                    if (dfs(j, l)) {
                        ans++;
                    }
                }
            }

            bw.append(ans + "\n");
            ans = 0;
        }

        br.close();
        bw.flush();
        bw.close();
    }
}

 

- 비슷한 유형의 풀이법이 외워져서 풀긴 했지만 처음으로 제대로 풀었다 ... 만족
- 조금 변형되서 다른 유형으로 나와도 풀 수 있을까 ?

 

 

1. 이전에 봤던 덩어리 묶어서 카운팅하는 유형과 비슷하다고 생각되어 dfs로 접근

2. 입력받은 graph 처음부터 끝까지 dfs를 수행한다.

2-1) 지렁이는 상하좌우로 움직일수 있으니 상하좌우로 움직이고 만약 범위가 벗어나면 false

2-2) 그래프를 순회하다가 1을 만나면 값을 0으로 바꿔줘서 중복이 안되게 하고 상하좌우에서 다시 dfs 호출

2-3) 이렇게 하면 한번 1을 만나면 거기서 상하좌우로 뻗어나갈 수 있는만큼 덩어리로 만들어주고 True return

3. return 되는 true수 만큼 ans++ 후에 출력 

 

 

 

---

www.acmicpc.net/problem/1012