유기농 배추

문제 정보

• 사이트 : 백준 알고리즘 사이트
• 문제 번호 : 1012
• 문제 분류 : dfs
• 난이도 : silver 2

문제 풀이

내가 짠 코드

생각한 문제 조건
1. 최소의 배추흰지렁이 구하기
2. 배추밭의 가로 M(1<=M<=50), 세로 N(1<=N<=50)
3. map의 1 = 배추 0 = 그냥 밭
4. 최대 최소 데이터 생각하기

• map이 1*1 인 경우
  • map[0][0]이 0인 경우 = 배추흰지렁이 0
  • map[0][0]이 1인 경우 = 배추흰지렁이 1
• map이 50*50인 경우(일반 경우랑 같음)

5. DFS로 풀었을 때 시간 복잡도

• DFS의 시간 복잡도 O(V+E)
• 정점의 최대 : O(N*M) = N^2
• 간선의 최대 : O(N*M*4) = 4N^2
• O(V+E) = O(N^2) N최대가 50이므로 DFS 사용가능(2500 < 1억)

💭 생각 노트

• map을 탐색하다 방문하지않았고 map[i][j]가 1인경우 dfs를 시작
• dfs가 시작한다는 것은 배추흰지렁이가 필요하다는 것이므로 result 증가
• map 전체의 탐색이 끝나면 result 출력

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int T,N,M,K,result;

    private static int[][] map;
    private static boolean[][] visit;
    private static int[][] check = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void input() throws IOException {
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);
        K = Integer.parseInt(input[2]);
        map = new int[N][M];
        visit = new boolean[N][M];
        result = 0;
        for (int i = 0; i < K; i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);
            map[x][y] = 1;
        }
    }

    public static void dfs(int x, int y){
        for (int i = 0; i < 4; i++) {
            int dx = x + check[i][0];
            int dy = y + check[i][1];

            if (0 <= dx && dx < N && 0 <= dy && dy < M) {
                if (!visit[dx][dy] && map[dx][dy] == 1) {
                    visit[dx][dy] = true;
                    dfs(dx,dy);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while(T-- > 0){
            input();
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(!visit[i][j] && map[i][j] == 1){
                        result++;
                        visit[i][j] = true;
                        dfs(i,j);
                    }
                }
            }
            System.out.println(result);
        }

        br.close();
    }
}

문제 출처

• 유기농 배추

썸네일 출처

Image by storyset on Freepik