[백준 1012번 / 유기농 배추 / JAVA]

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

1012번: 유기농 배추

 

문제 접근

 

DFS

2차원 배열을 만들어서 배추있는 지역에 1을 넣어주고, 방문했는지 판단을 위해 2차원 boolean 배열도 만들어 줌

배열을 돌면서 1을 발견하면 네 방향 탐색하면서 방문을 하지 않았고 1인 지역이 있다면 DFS로 타고 들어가서 계속 탐색한다.

연결된 모든 지역을 나비가 타고 들어가기에 1을 처음 발견했을 때만 나비 갯수를 카운트 해준다.

 

++

2차원 배열 공간의 크기를 지정해줄 때 세로, 가로 순으로 해야 떠올리기 편한데 문제에선 가로 값을 먼저 입력해야한다.

위치를 잘 바꿔주자

 

dx, dy로 네 방향 탐색하는 방법을 알고나니 참 편리하다.

 

import java.util.*;
import java.io.*;

public class Main {
	static int[][] cabbageFarm; // 배추 밭
	static boolean[][] visited; // 방문했던 지역 체크
	static int M, N, K;
	static int butterfly;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    
	    int T = Integer.parseInt(st.nextToken()); // 테스트 케이스

	    for(int t=0; t<T; t++) {
	    butterfly = 0;
	    // 2차원 배열로 생각하면 세로 가로 순으로 값을 넣어야 떠올리기 편한데 문제에선 가로 값 먼저 삽입한다.
	    st = new StringTokenizer(br.readLine());	
	    M = Integer.parseInt(st.nextToken()); // 가로
	    N = Integer.parseInt(st.nextToken()); // 세로
	    K = Integer.parseInt(st.nextToken()); // 배추 갯수
	    
	    cabbageFarm = new int[N][M];
	    visited = new boolean[N][M];
	    
	    // 배추 심기
	    for(int k=0; k<K; k++) {
	    	st = new StringTokenizer(br.readLine());
	    	int m = Integer.parseInt(st.nextToken());
	    	int n = Integer.parseInt(st.nextToken());
	    	cabbageFarm[n][m] = 1;
	    	
	    }
	    
	    // 나비 탐색
	     for(int i=0; i<N; i++) {
	    	 for(int j=0; j<M; j++) {
	    		 if(visited[i][j] == false && cabbageFarm[i][j] == 1) {
	    			 butterfly++;
	    			 dfs(i, j);
	    		 }
	    	 }
	     }
	     System.out.println(butterfly);
	   }
	}
	
	// 연결 배추 탐색
	private static void dfs(int x, int y) { // 여기선 지역을 방문했다 표시만
		visited[x][y] = true;
		
		for(int i=0; i<4; i++) {
			int plusX = x + dx[i]; // 위 아래
			int plusY = y + dy[i]; // 좌 우
			
			if(plusX < 0 || plusX >= N || plusY < 0 || plusY >= M) continue;
			
			if(visited[plusX][plusY] == false && cabbageFarm[plusX][plusY] == 1) { // 다음 지역을 방문하지 않았고 배추가 있다면
				dfs(plusX, plusY);
			}
			
		}
		
	}
}

 

 

BFS

DFS는 메소드 내에서 계속 DFS 메서드를 호출하지만 BFS는 네 방향을 일일이 확인하기위해 단 한 번의 호출 뒤 큐에 값을 넣고 while문 내에서 큐가 빌 때 까지 돌아간다.

 

++ 개인적인 느낌상 DFS가 뭔가 더 마음에 든다.

import java.util.*;
import java.io.*;

public class Main {
	static int[][] cabbageFarm; // 배추 밭
	static boolean[][] visited; // 방문했던 지역 체크
	static int M, N, K;
	static int butterfly;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };
	
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    
	    int T = Integer.parseInt(st.nextToken()); // 테스트 케이스

	    for(int t=0; t<T; t++) {
	    butterfly = 0;
	    // 2차원 배열로 생각하면 세로 가로 순으로 값을 넣어야 떠올리기 편한데 문제에선 가로 값 먼저 삽입한다.
	    st = new StringTokenizer(br.readLine());	
	    M = Integer.parseInt(st.nextToken()); // 가로
	    N = Integer.parseInt(st.nextToken()); // 세로
	    K = Integer.parseInt(st.nextToken()); // 배추 갯수
	    
	    cabbageFarm = new int[N][M];
	    visited = new boolean[N][M];
	    
	    // 배추 심기
	    for(int k=0; k<K; k++) {
	    	st = new StringTokenizer(br.readLine());
	    	int m = Integer.parseInt(st.nextToken());
	    	int n = Integer.parseInt(st.nextToken());
	    	cabbageFarm[n][m] = 1;
	    }
	    
	    // 나비 탐색
	     for(int i=0; i<N; i++) {
	    	 for(int j=0; j<M; j++) {
	    		 if(visited[i][j] == false && cabbageFarm[i][j] == 1) {
	    			 butterfly++;
	    			 bfs(i, j);
	    		 }
	    	 }
	     }
	     System.out.println(butterfly);
	   }
	}
	
	// 연결 배추 탐색
	private static void bfs(int x, int y) { // 여기선 지역을 방문했다 표시만
		Queue<int[]> q = new LinkedList<>();
		visited[x][y] = true;
		
		q.add(new int[] {x,y}); // 생성만 해놓기
		
		while(!q.isEmpty()) { // bfs는 큐에 값이 빌 때 까지 돌아가야함
		
			int[] arr = q.poll();
			
		for(int i=0; i<4; i++) {
			int plusX = arr[0] + dx[i]; // 위 아래
			int plusY = arr[1] + dy[i]; // 좌 우
			
			if(plusX < 0 || plusX >= N || plusY < 0 || plusY >= M) continue;
			
			if(visited[plusX][plusY] == false && cabbageFarm[plusX][plusY] == 1) { // 다음 지역을 방문하지 않았고 배추가 있다면
				visited[plusX][plusY] = true;
				q.add(new int[] {plusX, plusY});
			}
		  }
		}
	}
}