[BFS&DFS] 백준 - 유기농 배추

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

1012번: 유기농 배추

 

-문제해설

자바로는 BFS를 이용했고, 파이썬에서는 DFS를 이용했다.

 

 

 

 

-자바

package bfs_dfs;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
import java.awt.Point;

public class BJ1012 {
	private static int n, m;
	private static int[][] arr;
	private static int[] dx = { 0, 0, -1, 1 };
	private static int[] dy = { -1, 1, 0, 0 };
	
	private static void bfs( int a, int b ) {
		Queue<Point> que = new LinkedList<Point>();
		arr[a][b] = 0;
		que.add( new Point( a, b ) );
		
		int nx, ny;
		Point tmp;
		while( !que.isEmpty() ) {
			tmp = que.poll();
			
			for( int i=0; i<4; i++ ) {
				nx = tmp.x + dx[i];
				ny = tmp.y + dy[i];
				
				if( nx < 0 || ny < 0 || nx >= n || ny >= m )
					continue;
				
				if( arr[nx][ny] == 1 ) {
					arr[nx][ny] = 0;
					que.add( new Point( nx, ny ) );
				}
			}
		}
		
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt( br.readLine() );
		
		StringTokenizer st;
		int k, x, y, ans;
		StringBuilder sb = new StringBuilder();
		
		while( t-->0 ) {
			st = new StringTokenizer( br.readLine() );
			m = Integer.parseInt( st.nextToken() );
			n = Integer.parseInt( st.nextToken() );
			k = Integer.parseInt( st.nextToken() );
			
			arr = new int[n][m];
			while( k-->0 ) {
				st = new StringTokenizer( br.readLine() );
				x = Integer.parseInt( st.nextToken() );
				y = Integer.parseInt( st.nextToken() );
				arr[y][x] = 1;
			}
			
			ans = 0;
			for( int i=0; i<n; i++ ) {
				for( int j=0; j<m; j++ ) {
					if( arr[i][j] == 1 ) {
						bfs( i, j );
						ans++;
					}
				}
			}
			sb.append( ans ).append( "\n" );
		}
		System.out.println( sb );
	}
}

 

 

-파이썬

from sys import setrecursionlimit, stdin
setrecursionlimit( 99999 )

input = stdin.readline
t = int(input())

dr = [ -1, 0, 1, 0 ]
dc = [ 0, -1, 0, 1 ]

def dfs( row, col, n, m ):
    for i in range( 4 ):
        nrow = row + dr[i]
        ncol = col + dc[i]
        
        if ( 0 <= nrow < n ) and ( 0 <= ncol < m ) and arr[nrow][ncol] == 1:
            arr[nrow][ncol] = 0
            dfs( nrow, ncol, n, m )


for _ in range( t ):
    m, n, k = map(int, input().split())
    arr = [ [0]*m for _ in range( n ) ]
    
    for _ in range( k ):
        col, row = map(int, input().split())
        arr[row][col] = 1
    
    ans = 0
    for row in range( n ):
        for col in range( m ):
            if arr[row][col] == 1:
                arr[row][col] = 0
                ans += 1
                dfs( row, col, n, m )
    print( ans )