이코테 - 음료수 얼려 먹기(DFS)

코드)

public class Main{
	
	static int N; // 세로길이(1이상)
	static int M; // 가로길이(1000이하)
	
	// 얼음틀의 형태 입력
	public static int[][] ice_frame;
	
	// 구멍이 뚫려있는 노드에 인접한 모든 노드 방문처리
	public static boolean dfs(int x,int y) {
		
		// 주어진 범위를 벗어나는 경우(ex. 해당노드의 우측을 검사했을경우 노드가 없을경우)
		if(x<0 || x>=N || y<0 || y>=M) return false;	
		
		// 해당 노드의 상,하,좌,우에 구멍이 뚫려있는 노드가 있는지 검사
		if(ice_frame[x][y] == 0) {
			// 노드 방문처리 
			ice_frame[x][y] = 1;
			// 해당 노드의 상,하,좌,우 를 재귀적으로 호출하면서 방문처리 해줌 
			dfs(x-1,y); // 상 
			dfs(x+1,y); // 하
			dfs(x,y-1); // 좌
			dfs(x,y+1); // 우 
			return true;
		}
		return false;
	}
	
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt(); // 세로길이(1이상)
		M = sc.nextInt(); // 가로길이(1000이하)
		sc.nextLine(); // Enter 버퍼 지우기 
		
		// 얼음틀 만들기 
		ice_frame = new int[N][M];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				ice_frame[i][j] = sc.nextInt();
			}
		}
		
		// 아이스크림 만들기 
		int result = 0; // 만들어진 아이스크림 개수 
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(dfs(i,j)) {
					result++;
				}
			}
		}
		
		System.out.println(result);
	}

}

 

왜 이문제를 DFS로 접근을 하게 되었는가?? 

-> 해당 노드 그룹(구멍이 뚫려있는 부분)에 인접되는(상, 하, 좌, 우) 구멍이 뚫려있는 노드들을

찾는 작업을 수행하기 위한 과정이 하나의 노드에 대해서 가장 깊숙히 위치하는 노드에 닿을 때까지 탐색하는 DFS 방식이랑 유사함