1012번 : 유기농 배추

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

1012번: 유기농 배추

 

 

문제

 

 

코드

BFS

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

public class Main {
    static int [][] g;
    static int m,n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<t;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken()); 
            n = Integer.parseInt(st.nextToken()); 
            int k = Integer.parseInt(st.nextToken());
            g=new int[m][n];
            
            //배추 심기
            for(int j=0;j<k;j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                g[x][y] = 1;
            }
            
            //모든 칸 탐색 수행
            int count=0;
            for(int z=0;z<m;z++) {
                for(int l=0;l<n;l++) {
                    if(bfs(z,l)) count++;
                }
            }
            sb.append(count+"\n");
        }
        System.out.println(sb);
    }

    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static boolean bfs(int x, int y) {
        Queue<int[]> q = new LinkedList<>();
        if(g[x][y]==0) return false;
        q.add(new int[]{x,y});

        while(!q.isEmpty()) {
            int[] poll = q.poll();
            x = poll[0];
            y = poll[1];
            for(int i=0;i<4;i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx<0 || ny <0 || nx>=m || ny>=n) continue;
                if(g[nx][ny]==1) {
                    g[nx][ny]=0;
                    q.add(new int[]{nx,ny});
                }
            }
        }
        return true;
    }
}

DFS

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

public class Main {
    static int [][] g;
    static int m,n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<t;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            m = Integer.parseInt(st.nextToken()); 
            n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            g=new int[m][n];
            
            //배추 심기
            for(int j=0;j<k;j++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                g[x][y] = 1;
            }
            
            //모든 칸 탐색 수행
            int count=0;
            for(int z=0;z<m;z++) {
                for(int l=0;l<n;l++) {
                    if(dfs(z,l)) count++;
                }
            }
            sb.append(count+"\n");
        }
        System.out.println(sb);
    }

    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static boolean dfs(int x, int y) {
        if(g[x][y]==0) return false;
        g[x][y]=0;

        for(int i=0;i<4;i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx<0 || ny <0 || nx>=m || ny>=n) continue;
            if(g[nx][ny]==1) dfs(nx,ny);
        }
        return true;
    }

}

 

해결방법

BFS와 DFS 2가지 방식으로 풀었다. 어디에 배추에 심어져있을 지 모르기에 그래프의 모든 칸을 탐색하였고

지렁이가 갈 수 있는 범위 즉, 1로 이어진 부분이 있다면 너비 우선 탐색 또는 깊이 우선 탐색하여 0으로 바꾼 뒤 true를 반환하여 count를 증가시키는 방식으로 문제를 해결하였다.