[백준] 1012 유기농 배추

1. 문제

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

1012번: 유기농 배추

2. 접근방법

영역의 갯수를 구하는 문제.

 

bfs, dfs 기본 문제이지 않을까..

 

1. 전체 맵을 탐색하는데 맵의 값이 1이면 탐색 시작(나는 dfs 활용)

2. dfs를 돌며 값이 1인 위치만 들려 2로 변경(탐색 된 것을 표시)

3. 1번에서 탐색을 시작한 횟수를 카운트 하여 마지막에 출력.

3. 자바 코드

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

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        while (T-- > 0) {
            int area = 0;
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int map[][] = new int[m][n];
            while (k-- > 0) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }

            for(int i = 0 ; i < m ; i++){
                for(int j = 0 ; j < n ; j++){
                    if(map[i][j] == 1){
                        area++;
                        dfs(map,i,j);
                    }
                }
            }
            System.out.println(area);
        }
    }

    static int dr[] = new int[]{-1, 1, 0, 0};
    static int dc[] = new int[]{0, 0, -1, 1};

    public static void dfs(int map[][], int row, int col) {
        map[row][col] = 2;
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            if(newRow <0 || newCol < 0 || newRow >= map.length || newCol >= map[0].length) continue;
            if(map[newRow][newCol] != 1) continue;
            dfs(map,newRow,newCol);

        }
    }
}

4. 마치며

이전에 풀었던 문제인데 내배캠 문제로 있어서 재풀이했음.

 

이전에는 bfs에 visit 배열 이용했던데

dfs를 쓰면 방문 여부를 map에 바로 표현해도 되기 때문에 굳이 visit을 사용 안했음.