백준 1012 유기농 배추 (DFS, BFS)

1. 문제

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

 

2. 설명

앞에서 계속 풀어왔던 dfs bfs 기본 문제!

3차원 배열쓰고 나머지는 똑같이 풀었다.

이제 응용문제 풀어봐야징

 

3-1. dfs 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int[] goX = {-1, 1, 0, 0};
	static int[] goY = {0, 0, -1, 1};
	
	static void dfs(int T, int x, int y, int[][][] cabbage) {
		if(cabbage[T][x][y]==0) return;
		
		cabbage[T][x][y] = 0;
		for(int i=0; i<4; i++) {
			int nx = x + goX[i];
			int ny = y + goY[i];
			
			if(0<=nx && nx<cabbage[T].length && 0<=ny && ny<cabbage[T][0].length) {
				dfs(T,nx,ny,cabbage);
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // testcase 수
		int[][][] cabbage = new int[T][][]; // 가변 배열
		
		for(int i=0; i<T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken()); // 가로
			int N = Integer.parseInt(st.nextToken()); // 세로
			int K = Integer.parseInt(st.nextToken()); // 배추 위치 개수
			cabbage[i] = new int[M][N]; // 가로 세로에 맞춰 다시 메모리 생성
			
			for(int j=0; j<K; j++) {
				st = new StringTokenizer(br.readLine());
				int c1 = Integer.parseInt(st.nextToken());
				int c2 = Integer.parseInt(st.nextToken());
				cabbage[i][c1][c2] = 1; // 배추
			}
		}
		
		for(int i=0; i<T; i++) {
			int cnt = 0; // 배추 수 저장
			for(int j=0; j<cabbage[i].length; j++) { // 가로
				for(int k=0; k<cabbage[i][0].length; k++) { // 세로
					if(cabbage[i][j][k]==1) {
						dfs(i,j,k,cabbage);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
}

 

3-2. 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;

public class Main {
	static int[] goX = {-1, 1, 0, 0};
	static int[] goY = {0, 0, -1, 1};
	
	static void bfs(int T, int x, int y, int[][][] cabbage) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {x,y});
		cabbage[T][x][y] = 0;
		
		while(!q.isEmpty()) {
			int curX = q.peek()[0];
			int curY = q.peek()[1];
			q.poll();
			
			for(int i=0; i<4; i++) {
				int nx = curX + goX[i];
				int ny = curY + goY[i];
				
				if(0<=nx && nx<cabbage[T].length && 0<=ny && ny<cabbage[T][0].length) {
					if(cabbage[T][nx][ny] == 1) {
						q.add(new int[] {nx,ny});
						cabbage[T][nx][ny] = 0;
					}
				}
			}
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine()); // testcase 수
		int[][][] cabbage = new int[T][][]; // 가변 배열
		
		for(int i=0; i<T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int M = Integer.parseInt(st.nextToken()); // 가로
			int N = Integer.parseInt(st.nextToken()); // 세로
			int K = Integer.parseInt(st.nextToken()); // 배추 위치 개수
			cabbage[i] = new int[M][N]; // 가로 세로에 맞춰 다시 메모리 생성
			
			for(int j=0; j<K; j++) {
				st = new StringTokenizer(br.readLine());
				int c1 = Integer.parseInt(st.nextToken());
				int c2 = Integer.parseInt(st.nextToken());
				cabbage[i][c1][c2] = 1; // 배추
			}
		}
		
		for(int i=0; i<T; i++) {
			int cnt = 0; // 배추 수 저장
			for(int j=0; j<cabbage[i].length; j++) { // 가로
				for(int k=0; k<cabbage[i][0].length; k++) { // 세로
					if(cabbage[i][j][k] == 1) {
						bfs(i,j,k,cabbage);
						cnt++;
					}
				}
			}
			System.out.println(cnt);
		}
	}
}