[JAVA]BOJ(백준) - 유기농 배추 - 1012

- 문제 내용

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

1012번: 유기농 배추

---

 

- 문제 접근 방법

가장 먼저 집단화된 배추들의 개수를 알수있다면 배추벌레의 수도 알 수 있다.

그래서 단지번호붙이기(2667)처럼 집단 하나하나를 dfs로 세다보면 답이나온다.

필요한 것들 -> 방문배열, 배추맵, 벌레수 세주는 변수, count한 벌레 넣을 리스트, 상하좌우 배열

 

여튼 단지번호붙이기(2667) 문제와 비슷데 이문제가 더 간단하다고 생각하고 입력값에 대해 어떻게 함수를 어떻게 돌릴지만 생각하면 되는 문제라고 생각했다!

---

- 풀이

• 선언값

	static int T; //테스트 케이스
	static int M; //배추밭 가로길이
	static int N; //배추밭 세로길이
	static int K; //배추가 심어져있는 위치의 개수
	static int k1; //K 위치의 x좌표
	static int k2; //K 위치의 y좌표
	
	static boolean[][] check; //방문배열
	static int[][] bachuMap; //배추밭
	static int[] x = {0, 0, -1, 1}; //상하좌우
	static int[] y = {-1, 1, 0, 0}; //상하좌우
	static int bugCnt; //지렁이 마리수
	static ArrayList<Integer> result; //각 테스트 케이스 지렁이들을 넣을 리스트

 

• main

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		result = new ArrayList<Integer>();
		T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {//테스트 케이스 만큼 돌려~
			//각 테케마다 값들을 초기화
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			bachuMap = new int[M][N];
			check = new boolean[M][N];
			
			for(int k=0; k<K; k++) {//K개만큼 심어져있는 배추위치로 배열에 1넣기~
				st = new StringTokenizer(br.readLine());
				k1 = Integer.parseInt(st.nextToken());
				k2 = Integer.parseInt(st.nextToken());
				
				bachuMap[k1][k2]=1;
			}//for
			
			bugCnt=0;//배추벌레 0으로 초기화
			new BOJ_1012().solution(); 
			result.add(bugCnt);//함수 끝났을때 리스트에 해당 테스트케이스 배추벌레 추가~
		}//for
		
		for(int resultCnt:result) { 
			System.out.println(resultCnt); //출력
		}
	}

 

• 함수 부분

	public void solution() {
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(bachuMap[i][j]==1 && !check[i][j]) {
					dfs(i,j); //조건에 맞으면 i,j부터 dfs 시작
					bugCnt++; //dfs가 끝나면 벌레수 증가
				}//if
			}//for
		}//for
	}//solution
	
	public void dfs(int v1, int v2) {
		check[v1][v2]=true; //방문한 배추는 true 처리
		
		for(int i=0; i<4; i++) {
			int dx = v1 + x[i]; // v1,v2 좌표에서 좌우 좌표를 변경
			int dy = v2 + y[i]; // v1,v2 좌표에서 상하 좌표를 변경
			
			if(dx>=0 && dy>=0 && dx<M && dy<N) {
				if(bachuMap[dx][dy]==1 && !check[dx][dy]) {
					dfs(dx,dy); //변경된 좌표가 조건에 맞다면 dfs로 다시 탐색
				}//if
			}//if
		}//for
	}//dfs

 

• 전체코드

package org.boj.dfs.bfs;

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

/**
 * soution 함수는 배추밭의 모여있는 배추집단 하나하나 확인하는 거라고 생각
 * dfs 함수는 모여있는 배추집단 하나가 어디까지 이어져있는지 확인하는 거라고 생각.
 * 
 * 배추집단 하나 확인했다면 거기엔 벌레 1마리 있는거임 ㅇㅇ.
 */

public class BOJ_1012 {
	static int T; //테스트 케이스
	static int M; //배추밭 가로길이
	static int N; //배추밭 세로길이
	static int K; //배추가 심어져있는 위치의 개수
	static int k1; //K 위치의 x좌표
	static int k2; //K 위치의 y좌표
	
	static boolean[][] check; //방문배열
	static int[][] bachuMap; //배추밭
	static int[] x = {0, 0, -1, 1}; //상하좌우
	static int[] y = {-1, 1, 0, 0}; //상하좌우
	static int bugCnt; //지렁이 마리수
	static ArrayList<Integer> result; //각 테스트 케이스 지렁이들을 넣을 리스트
	
	public void solution() {
		for(int i=0; i<M; i++) {
			for(int j=0; j<N; j++) {
				if(bachuMap[i][j]==1 && !check[i][j]) {
					dfs(i,j); //조건에 맞으면 i,j부터 dfs 시작
					bugCnt++; //dfs가 끝나면 벌레수 증가
				}//if
			}//for
		}//for
	}//solution
	
	public void dfs(int v1, int v2) {
		check[v1][v2]=true; //방문한 배추는 true 처리
		
		for(int i=0; i<4; i++) {
			int dx = v1 + x[i]; // v1,v2 좌표에서 좌우 좌표를 변경
			int dy = v2 + y[i]; // v1,v2 좌표에서 상하 좌표를 변경
			
			if(dx>=0 && dy>=0 && dx<M && dy<N) {
				if(bachuMap[dx][dy]==1 && !check[dx][dy]) {
					dfs(dx,dy); //변경된 좌표가 조건에 맞다면 dfs로 다시 탐색
				}//if
			}//if
		}//for
	}//dfs
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		result = new ArrayList<Integer>();
		T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {//테스트 케이스 만큼 돌려~
			//각 테케마다 값들을 초기화
			st = new StringTokenizer(br.readLine());
			M = Integer.parseInt(st.nextToken());
			N = Integer.parseInt(st.nextToken());
			K = Integer.parseInt(st.nextToken());
			
			bachuMap = new int[M][N];
			check = new boolean[M][N];
			
			for(int k=0; k<K; k++) {//K개만큼 심어져있는 배추위치로 배열에 1넣기~
				st = new StringTokenizer(br.readLine());
				k1 = Integer.parseInt(st.nextToken());
				k2 = Integer.parseInt(st.nextToken());
				
				bachuMap[k1][k2]=1;
			}//for
			
			bugCnt=0;//배추벌레 0으로 초기화
			new BOJ_1012().solution(); 
			result.add(bugCnt);//함수 끝났을때 리스트에 해당 테스트케이스 배추벌레 추가~
		}//for
		
		for(int resultCnt:result) { 
			System.out.println(resultCnt); //출력
		}
	}
}

---

- 마치며

단지번호붙이기(2667)을 풀었다면 쉬운 문제이다. 2667문제를 다시 복습해보자!

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

2667번: 단지번호붙이기