[백준 BOJ] 1012번 유기농 배추 (Java)

문제 설명

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

1012번: 유기농 배추

 

접근 방법 - 깊이 우선 탐색 (DFS)

백준의 1012번 문제는 DFS 및 BFS 문제이다. 필자는 DFS로 문제를 해결하였다.

필자는 아래의 흐름대로 규칙을 설정하고 코드를 작성해보았다.

 

필자는 배열을 이용할 시, 아래의 규칙을 정해두고 배열의 값을 바꾸었다.

  0 : 배추가 없음

  1 : 배추가 있음 & 지렁이가 방문하지 않음

  2 : 배추가 있음 & 지렁이가 이미 방문함

 

코드의 실행 순서

1) 테스트 케이스 개수 입력받기 (+그 수만큼 전체 반복문 실행)

 

2) 가로 52, 세로 52인 배열 선언 및 전체적으로 0으로 초기화

(실제로 최대로 입력되는 것은 50*50이지만 DFS 알고리즘 수행할 시 상하좌우로 각각 1칸씩 여유가 되도록 하였다.)

 

3) 가로 및 세로, 배추의 개수, 각 배추의 위치를 순차적으로 입력받기 (+입력받은 배추의 위치의 값을 1로 바꾸기)

 

4) 최소로 사용하는 지렁이 개수 측정 위해 DFS 알고리즘 사용

지렁이가 방문하지 않았고 배추가 있는 한 좌표에 지렁이 하나를 놓은 뒤,

loof() 함수로 이 지렁이가 접근 가능한 공간을 확인한다.

loof() 함수 : 현 위치 및 상하좌우로, 지렁이 하나가 접근할 수 있는 공간들 모두, 방문했다는 의미로 2로 표시하는 함수

(재귀 함수로 구현하여 지렁이 하나가 방문할 수 있는 모든 영역을 검사한다.)

 

5) 최소로 사용한 지렁이의 개수를 출력한다. 그리고 종료한다.

반응형

 

성공한 코드

import java.util.Scanner;
//백준 1012번 코드
public class Main {
	static int a[][]=new int [100][100];
	public static void Loof(int k, int t) {
		if(a[k][t]==1) {
			a[k][t]++;
		}
		if(a[k][t+1]==1) {
			a[k][t+1]++;
			Loof(k,t+1);
		}
		if(a[k][t-1]==1) {
			a[k][t-1]++;
			Loof(k,t-1);
		}
		if(a[k+1][t]==1) {
			a[k+1][t]++;
			Loof(k+1,t);
		}
		if(a[k-1][t]==1) {
			a[k-1][t]++;
			Loof(k-1,t);
		}
	}
	public static void main(String args[]) {
		Scanner s=new Scanner(System.in);
		int test1=s.nextInt();//테스트 케이스 개수
		
		int count;//테스트 케이스 카운트 변수
		for(count=0;count<test1;count++) {
			//입력부분
			for(int i=0;i<52;i++) {//i:열
				for(int j=0;j<52;j++) {//j:행
					a[i][j]=0;
				}
			}//배열 초기화
			
			//입력부분
			int w=s.nextInt();//가로길이 -> 행
			int l=s.nextInt();//세로길이 -> 열
			int n=s.nextInt();//배추 개수 
			for(int i=0;i<n;i++) {//배추 개수만큼 좌표입력 받기
				int x=s.nextInt();//x좌표 -> 행
				int y=s.nextInt();//y좌표 -> 열
				a[y+1][x+1]=1;
			}//배추 표시
			
			//탐색부분
			//0: 배추없음, 1:배추있음, 2:배추있음(방문완료)
			int num=0;//지렁이 수 -> 출력 변수
			for(int i=1;i<l+1;i++) {
				for(int j=1;j<w+1;j++) {
					if(a[i][j]==1) {
						num++;
						Loof(i,j);
					}
				}//for문 끝
			}//2중 for문 끝
			System.out.println(num);
		}//테스트 케이스 for문 끝
		System.exit(0);
	}
}

 

제출 결과

(2020.01.20 백준 1012번 제출 결과)

(첫 DFS 문제여서 그런지 많이 헤맸던 게 보인다. 심지어 지금 보니 코드도 많이 엉망진창이다. 다음에 풀 땐 제대로 해야지.)