1012 유기농배추

BOJ::1012 유기농배추

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

BLOB의 갯수를 구하는 문제(사실 BLOB이라는 표현이 맞는표현인지는 잘 모르겠다..ㅎㅎㅎ)

BFS, DFS 이용하는 기본적인 문제

단순히 탐색하며 카운트만 증가시키면 되기 때문에 dfs로 코딩하는게 더 쉽고 빠른거 같다.

(실제 채점현황에서 속도 차이는 없음)

DFS를 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main{
    
    static int t,n,m,k,ax,ay;
    static int map[][]=new int[51][51];
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        
        for(int z = 0 ; z < t ; z++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            n=Integer.parseInt(st.nextToken());
            m=Integer.parseInt(st.nextToken());
            k=Integer.parseInt(st.nextToken());
            for(int i = 0 ; i < k ; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y]=1;
            }
            
            int cnt=0;
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j < m ; j++){
                    if(map[i][j]==1){
                        cnt++;
                        dfs(i,j);
                    }
                }
            }
            System.out.println(cnt);
        }
    }
    
    //깊이우선탐색
    public static void dfs(int a,int b){
        map[a][b]=0;
        for(int i = 0 ; i < 4 ; i++){
            ax = a+dx[i];
            ay = b+dy[i];
            if((ax>=0&&ay>=0&&ax<n&&ay<m) && map[ax][ay]==1){
                dfs(ax,ay);
            }
        }
    }
    
}
 
 
 

BFS를 이용한 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main{
    
    static int t,n,m,k,ax,ay,x,y;
    static int map[][]=new int[51][51];
    static int dx[]={1,-1,0,0};
    static int dy[]={0,0,1,-1};
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        t = Integer.parseInt(br.readLine());
        
        for(int z = 0 ; z < t ; z++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            n=Integer.parseInt(st.nextToken());
            m=Integer.parseInt(st.nextToken());
            k=Integer.parseInt(st.nextToken());
            for(int i = 0 ; i < k ; i++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y]=1;
            }
            
            int cnt=0;
            for(int i = 0 ; i < n ; i++){
                for(int j = 0 ; j < m ; j++){
                    if(map[i][j]==1){
                        cnt++;
                        bfs(i,j);
                    }
                }
            }
            System.out.println(cnt);
        }
    }
    
    public static void bfs(int a,int b){
        map[a][b]=0;
        
        Queue<Node> q = new LinkedList();
        q.add(new Node(a,b));
        while(!q.isEmpty()){
            x = q.peek().x;
            y = q.poll().y;
            
            for(int i = 0 ; i < 4 ; i++){
                ax = x+dx[i];
                ay = y+dy[i];
                if((ax>=0&&ay>=0&&ax<n&&ay<m)&&map[ax][ay]==1){
                    map[ax][ay]=0;
                    q.add(new Node(ax,ay));
                }
            }
        }
    }
}
 
class Node{
    int x;
    int y;
    Node(int _x, int _y){
        x=_x;
        y=_y;
    }
}