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)