[백준] 1012번 유기농 배추

 

문제 (DFS)

 

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

 

 

문제 풀이

 

알고리즘 오랜만에 푸는 거라 실버2 만만한 DFS 골라서 풀었는데 사소한 조건들 다 잘못해서 푸는 데 한참 걸렸다.

 

내가 실수한 부분: (ㅠㅠ)

 1. M = 가로길이 / N = 세로길이 →  보통 문제 풀 때 무조건 순서대로 행/열 이라고 생각해서 풀어서 실수

 2. DFS 조건 돌릴 때 변수 > 0  표시할 때 >= 이꼴도 들어갔어야 했는데 =안하고 계속 어디서 실수지 Print로 한참 쳐보다가 발견함..

 

간단한 문제풀이 설명:

반복 돌리면서 양배추 구간을 만나면 DFS로 최대 양배추 구간을 구해 Vist 표시 후에 뭉텅이 개수 구해서 return.

 

 

소스 코드

 

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

public class Main {

	static int[] dn = {0, 0, -1, 1};
	static int[] dm = {1, -1, 0, 0};
	
	static int[][] cabbage;
	static boolean[][] visited;
	static int M, N, total;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int t = 0; t < T; t++) {
			String[] str = br.readLine().split(" ");
			M = Integer.parseInt(str[0]);
			N = Integer.parseInt(str[1]);
			cabbage = new int[N][M];
			visited = new boolean[N][M];
			int K = Integer.parseInt(str[2]);
			
			for(int i = 0; i < K; i++) {
				String[] s = br.readLine().split(" ");
				cabbage[Integer.parseInt(s[1])][Integer.parseInt(s[0])] = 1;
			}
			
			total = 0;
			solution(cabbage);
		}
	}
	
	public static void solution(int[][] cabbage) {
		for(int n = 0; n < N; n++) {
			for(int m = 0; m < M; m++) {
				if(cabbage[n][m] == 1 && !visited[n][m]) {
					DFS(n, m);
					total++;
				}
			}
		}
		
		System.out.println(total);
	}
	
	public static void DFS(int n, int m) {
		visited[n][m] = true;
		
		for(int i = 0; i < 4; i++) {
			int nx = n + dn[i];
			int ny = m + dm[i];
			
			if(nx >= 0 && ny >= 0 && nx < N && ny < M) {
				if(cabbage[nx][ny] == 1 && !visited[nx][ny])
					DFS(nx, ny);
			}
		}
	}
	
}