[伯俊]2012号オーガニック白菜/Java,Python


Baekjoon Online Judge


algorithm practice


-問題を逐次解く


24.DFSとBFS


グラフを巡るアルゴリズムを学びましょう.
Java/Python

4.有機白菜


1012号
白菜の位置問題

この問題は白菜畑に必要な白菜の白ミミズを探す問題です.
  • Java
  • DFSを使用してこの問題を解決しました.
    dfs(int x,int y):
    1.現在のノードにアクセスします.
    2.現在のノードから上、下、左、右のノードに移動できることを確認します.(可能であれば、dfs()を呼び出して、範囲外であるかどうか、白菜が存在するかどうかを決定します.)
    import java.io.*;
    import java.util.*;
    
    public class Main {
    	static int N, M;
    	static boolean[][] arr;
    	static boolean[][] check;	// 방문 여부
        
    	public static void main(String[] args) throws IOException {
    		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    		int T = Integer.parseInt(br.readLine());
    		int result;        
            
    		for(int i = 0; i < T; i++){
    			StringTokenizer st = new StringTokenizer(br.readLine());
    			M = Integer.parseInt(st.nextToken());	
    			N = Integer.parseInt(st.nextToken());
    			int cnt = Integer.parseInt(st.nextToken());      
            
    			arr = new boolean[N][M];      
    			check = new boolean[N][M];
    			result = 0;
            
    			for(int j = 0; j < cnt; j++){
    				st = new StringTokenizer(br.readLine());
    				int x = Integer.parseInt(st.nextToken());
    				int y = Integer.parseInt(st.nextToken());
    				arr[y][x] = true;
    			}
                
    			for(int j = 0; j < N; j++){
    				for(int k = 0; k < M; k++){
    					if(checkLocation(j, k)){
    						result++;
    						dfs(j, k);
    					}
    				}
    			}
    			bw.write(result + "\n");
    		}
            
    		bw.flush();
    		bw.close();
    		br.close();
    	}
    	public static boolean checkLocation(int row, int col){
    		// 좌표 값이 잘못된 경우
    		if(row < 0 || row >= N || col < 0 || col >= M) return false;
    		// 이미 지나간 경로인 경우 || 집이 아닌 경우
    		if(check[row][col] || !arr[row][col]) return false;
    		return true;
    	}
    	public static void dfs(int x, int y){
    		check[x][y] = true;
            
    		// '상'의 좌표
    		if(checkLocation(x - 1, y)) dfs(x - 1, y);
    		// '하'의 좌표
    		if(checkLocation(x + 1, y)) dfs(x + 1, y);
    		// '좌'의 좌표
    		if(checkLocation(x, y - 1)) dfs(x, y - 1);
    		// '우'의 좌표
    		if(checkLocation(x, y + 1)) dfs(x, y + 1);
    	}
    }
  • Python
  • import sys 
    sys.setrecursionlimit(10000) 
    T = int(sys.stdin.readline()) 
    
    def dfs(x, y): 
        dx = [1, -1, 0, 0] 
        dy = [0, 0, 1, -1] 
        
        # 상,하,좌,우 확인 
        for i in range(4): 
            nx = x + dx[i] 
            ny = y + dy[i] 
            if (0 <= nx < N) and (0 <= ny < M): 
                if arr[nx][ny] == 1: 
                    arr[nx][ny] = -1 
                    dfs(nx, ny) 
                    
    for _ in range(T): 
        M, N, K = map(int, sys.stdin.readline().split()) 
        arr = [[0]*M for _ in range(N)] 
        cnt = 0 
        
        # 행렬 생성 
        for _ in range(K): 
            a, b = map(int, sys.stdin.readline().split()) 
            arr[b][a] = 1 
            
        for i in range(N): # 행 (바깥) 
            for j in range(M): # 열 (내부) 
                if arr[i][j] > 0: 
                    dfs(i, j) 
                    cnt += 1 
                    
        print(cnt)