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

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

 

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

public class Main {
    public static int T, M, N, K, ans;
    public static int[][] map, visited;
    public static int[] dr = {-1, 0, 1, 0};
    public static int[] dc = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        for (int tc = 1; tc <= T; tc++) {
            // 1. 입력받기
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            map = new int[M][N];
            visited = new int[M][N];
            ans = 0;
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int r = Integer.parseInt(st.nextToken());
                int c = Integer.parseInt(st.nextToken());
                map[r][c] = 1;
            }

            // 2. dfs 탐색
            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 1 && visited[i][j] == 0) { // 방문한 적이 없다면
                        dfs(i, j);
                        ans++;

                    }
                }
            }

            // 3. 출력하기
            System.out.println(ans);
        }
    }

    public static void dfs(int i, int j) {
        visited[i][j] = 1;

        for (int d = 0; d < 4; d++) {
            int nr = i + dr[d];
            int nc = j + dc[d];
            if (nr < 0 || nr >= M || nc < 0 || nc >= N || visited[nr][nc] == 1 || map[nr][nc] == 0) continue;
            dfs(nr, nc);
        }
    }
}

 

풀이 사항

풀이 일자: 2025.01.06
풀이 시간: 30분
채점 결과: 정답
예상 문제 유형: dfs
시간: 136ms
메모리:15884KB

풀이방법

단지번호 붙이기와 비슷한 로직을 사용하였다.

1. 맵 정보를 2차원 만들어서 배추 정보를 1로 초기화, visited배열도 함께 만들어주고 0으로 초기화 한다.
2. 이중 포문으로 맵을 다시 차례로 돌며 map[r][c]가 1이고 visited[r][c]가 0인경우 (배추가 있고 방문하지 않은경우 dfs탐색을 하고 ans 증가
3. dfs함수는 들어오자마자 visited 배열을 1로 바꿔주고 (방문처리) 상하좌우를 확인해서 맵을 벗어나지 않고 배추가 있고 방문하지 않은 구역이라면 재귀해준다.
4. ans를 출력한다.