[백준,BOJ 1012] 유기농 배추(JAVA 구현,추가풀이)

-내 생각

  DFS, BFS 분류가 되어있는 유기농 배추 문제이다. 문제 자체는 백준 2667 단지 번호 붙이기와 다르게 보이지만, 사실상 같은 문제라고 생각했다. 단지 번호 붙이기 같은 경우에는 인접한 아파트의 수를 카운트하는 것이라면, 이 문제는 인접한 배추의 묶음단위를 카운트하는 것이었다. 그렇기 때문에 DFS를 이용해 깊이를 우선하여 완전 탐색을 실시해 풀 수 있다고 생각했다.

 

-해법

  코드의 내용은 단지번호 붙이기에서 약간만 수정해주면 된다.

import java.util.*;



public class Main {
	static int node[][]; // 배추밭 배열
	static int check[][]; // 배추방문 배열
	static int cnt =0; // 배추의 묶음을 카운트 할 변수
	
	
	static ArrayList<Integer> array = new ArrayList<>(); // 각 테스트케이스마다의 결과를 저장할 어레이 리스트
	
		static void dfs(int x,int y) { // DFS탐색을 수행 할 메소드
			
			check[x][y] =1; // 방문여부 표시
			

				// 기준점의 동서남북을 확인한다 자세한 코드설명은 단지번호 붙이기를 참고
				if( y<node[x].length-1 && node[x][y+1]==1 && check[x][y+1]==0) {
					
					
					dfs(x,y+1);				
				}
								
				 if(x<node.length-1 && node[x+1][y]==1&& check[x+1][y]==0) {
					
					
					dfs(x+1,y);
				}
				
				 if(y>0 &&  node[x][y-1]==1&& check[x][y-1]==0) {
					
					
					dfs(x,y-1);
					
				}
				 if(x>0 &&  node[x-1][y]==1&& check[x-1][y]==0) {
					
						
					dfs(x-1,y);
					
				}		
	
	}
			
			
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);	
		
		int t= sc.nextInt(); // 테스트 케이스
		
		
		for(int i=0;i<t;i++) {
			int m = sc.nextInt(); // 배추밭 가로길이
			int n = sc.nextInt(); // 배추밭 세로길이
			int k = sc.nextInt(); // 배추 개수
			
			node = new int[n][m];
			check = new int[n][m];
			cnt=0;
			
			for(int j=0;j<k;j++) { // 배추 위치 입력
				int a = sc.nextInt();
				int b = sc.nextInt();				
				node[b][a] = 1;
			}
            
			for(int j=0;j<node.length;j++) {
				for(int g=0;g<node[j].length;g++) {
					if(node[j][g] == 1 && check[j][g]==0) { // 배추가 심어져있고 방문하지 않았던 배추를 인자로 전달
						
						cnt++; // 배추의 묶음마다 cnt증가
						dfs(j,g);
						
					}
				}
			}
			
			array.add(cnt); // 테스트케이스마다 배추의 묶음 수를 저장
			
		}
		
		
		for(int i=0;i<array.size();i++) { // 출력
			System.out.println(array.get(i));
		}
	
		
	}
	
}

---

  단지 번호 붙이기와 같은 유형의 문제이다. 역시 BFS를 이용해 풀어보았다.

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

class Dot{
		int x;
		int y;
		
		public Dot(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}
		
		public int getX() {
			return x;
		}
		public void setX(int x) {
			this.x = x;
		}
		public int getY() {
			return y;
		}
		public void setY(int y) {
			this.y = y;
		}				
}

class Main {
  
  	static int num = 0;
  	static int dx[] = {1,-1,0,0};
    static int dy[] = {0,0,1,-1};
	static void bfs(int[][] a, boolean[][] check, Dot d) {
		Queue<Dot> q = new LinkedList<>();
		
		
		q.offer(d);
		check[d.getX()][d.getY()] = true;
		
		while(!q.isEmpty()) {
			Dot d_p = q.poll();
			int x = d_p.getX();
			int y = d_p.getY();
			
			
			for(int i=0;i<4;i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				
				if(nx>=a.length || nx<0 || ny>=a[nx].length || ny < 0) continue;
				
				if(check[nx][ny]) continue;
				
				if( a[nx][ny] == 1){					
					check[nx][ny] = true;
					q.offer(new Dot(nx,ny));
				}
			}			
		}
		
		
		
	}
	
	public static void main(String[] args)  {
		Scanner in = new Scanner(System.in);
		
		int t = in.nextInt();
		
		
		int map[][] ;
		boolean check[][];
		
		Dot d;
		
		for(int i = 0; i<t; i++) {
			int m =in.nextInt(); // 가로
			int n = in.nextInt(); // 세로
			int k = in.nextInt(); // 배추 수
			map = new int[m][n]; // 배추 밭 생성
			check = new boolean[m][n]; // 방문 여부 체크 배열
			
			for(int j = 0;j<k;j++) { // 배추 좌표 입력
				map[in.nextInt()][in.nextInt()] = 1;
			}
			for(int q =0;q<map.length;q++) {
				for(int w =0; w<map[q].length;w++) {
					if(map[q][w] == 1 && check[q][w] == false) { // 배추가 있고 방문하지 않았다면
						d = new Dot(q,w);
						bfs(map,check,d); // 해당 좌표부터 BFS 수행
						num++; // 수행한 뒤 지렁이 수 증가
					}
				}				
			}
			System.out.println(num);
			num = 0;
		}		
	  }
}