[코딩테스트]DFS(음료수 얼려 먹기)

책 '이것이 취업을 위한 코딩 테스트다'를

기반으로 공부하였습니다.

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체

 

1. 음료수 얼려먹기

입력조건

- 첫 번째 줄에 얼음 틀의 세로 길이N과 가로 길이M이 주어진다. (1<=N,M<=1000)

- 두 번째 줄부터 N+1번째 줄까지 얼음틀의 형태가 주어진다.

- 이때 구멍이 뚫려있는 부분은 0, 그렇지 않은 부분은 1이다.

출력조건

- 한 번에 만들 수 있느 아이스크림의 개수를 출력한다.

 

작성코드(JAVA)

import java.util.*;

public class test8_DFS {
		
	static int [][] a;
	static int count = 0;
	static int n,m;
	
	public static int dfs(int num,int num2) {
		int temp =0;
		if((num)>-1&&(num)<n&&(num2)>-1&&(num2)<m) {
			if(!(a[num][num2]==1)) {
				a[num][num2] =1;
				dfs(num-1,num2);
				dfs(num+1,num2);
				dfs(num,num2-1);
				dfs(num,num2+1);
				temp=1;
				return temp;
			}
		}
		return temp;
		
	}
	
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);

		n=kb.nextInt();
		m=kb.nextInt();
		
		a = new int[n][m];
		
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				a[i][j] = kb.nextInt();
			}
		}
		for(int k=0;k<n;k++) {
			for(int l=0;l<m;l++) {
				count+=dfs(k,l);
			}
		}
		System.out.println(count);
	}

}

설명

- 해당 문제는 DFS로 접근하면 풀수 있는 문제입니다. 우선 얼음을 만들 수 있는 공간이 0이고 나머지 틀을 구성하는 부분이 1입니다. DFS를 이용하여 모든 공간에 DFS를 적용하는데 DFS를 거친 공간은 1로 바꾸어주며, 해당 공간에서의 DFS를 끝마치면 count에 1을 더하여 얼음이 몇개가 생성될 수 있는지 표현합니다. DFS는 재귀함수로 표현하였으며 해당 인덱스를 넘어가면 안되므로 해당 범위내에서 DFS가 수행되도록 조건식을 달아놓습니다.

 

 

( DFS함수에서 리턴값을 굳이 temp를 쓰지않고 return 1; 과 return 0; 으로 해도 될 것 같습니다. 30분만에 코드를 작성해야 되는데 리턴값을 어떻게 넘겨줄까 고민을 너무 많이한거 같습니다ㅠㅠ 40분정도 걸렸네요 더욱 힘내서 30분 안에 코드 작성할 수 있도록 노력하겠습니다! )