[DFS/BFS] 문제이름 : 음료수 얼려 먹기

문제 설명

N X M 크기의 얼음 틀이 있다. 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다. 구멍이 뚫려 있는 부분끼리 상 하 좌 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 

 

1. 사용 알고리즘 

그래프 탐색 - BFS & DFS 

 

2. 문제 해결 아이디어 

주어진 좌표의 위치와 해당 위치의 상하좌우에 대해 구멍이 뚫려서 연결되어 있는지 탐색하면 된다. 이때 주어진 2차원 배열을 그래프 형태로 생각하면, DFS와 BFS 알고리즘을 적용해 해결할 수 있다.  

 

3. 코드

구현방식1) BFS(너비 우선 탐색)를 사용해 가까운 좌표부터 확인하기

각 좌표가 상하좌우에 대해 움직일 수 있는 좌표의 범위를 dx[], dy[] 리스트로 미리 선언해둔다. 

main 메서드 내에서 이중for문으로 주어진 좌표의 모든 위치에 대해 hole(구멍이 뚫린 부분)인 경우 BFS를 실행한다. 

bfs 함수 내에서

주어진 좌표의 row와 col을 각각 큐에 저장(enqueue) -> row와 col 값 꺼내기(dequeue) -> 주어진 좌표의 상하좌우에 대해        hole(구멍이 뚫린 경우)인 경우 큐에 저장(enqueue) -> 방문했음을 체크하기 위해(main에서 해당 좌표에 대해 bfs() 호출하지 않도록 하기 위해) visited로 설정

import java.util.LinkedList;
import java.util.Queue;

import java.util.Scanner;

public class Ex1 {
	public static int mapRowSize, mapColSize;
	
	public static int dx[] = {-1, 1, 0, 0}; //행의 움직임 (상하좌우)
	public static int dy[] = {0, 0, -1, 1}; //열의 움직임 (상하좌우) 
	
	public static int hole = 0, wall = 1, visited = 2;
	
	public static void bfs(int iceMap[][], int startVertexRow, int startVertexCol) { 
		Queue<Integer> rowQueue = new LinkedList<Integer>();
		Queue<Integer> colQueue = new LinkedList<Integer>();
		
		rowQueue.offer(startVertexRow); //enqueue
		colQueue.offer(startVertexCol);
		iceMap[startVertexRow][startVertexCol] = visited; 
		
		while(!rowQueue.isEmpty()) {
			startVertexRow = rowQueue.poll(); //dequeue 
			startVertexCol = colQueue.poll();
			
			for(int i = 0; i < dx.length; i++) {
				int x = startVertexRow + dx[i]; //row -> 헷갈린 부분 : x가 좌표에서의 x값이 아니라 행임! 
				int y = startVertexCol + dy[i]; //col -> y는 열임! 
				
				if(x != -1 && x != mapRowSize && y != -1 && y != mapColSize) { //x좌표 -> col, y좌표 -> row 
					if(iceMap[x][y] == hole) {
						rowQueue.offer(x);
						colQueue.offer(y); 
						iceMap[x][y] = visited; 
					}
				}
			}
		}
	}
	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		mapRowSize = kbd.nextInt();
		mapColSize = kbd.nextInt();
		kbd.nextLine(); //버퍼 지우기 
		
		int iceMap[][] = new int[mapRowSize][mapColSize]; //그래프의 경우 -> 인접행렬이라고 생각하기 
		
		/* 2차원 리스트의 맵 정보 입력 받기 */
		for(int i = 0; i < mapRowSize; i++) {
			String str = kbd.nextLine(); //문자열로 입력받기 
			for(int j = 0; j < mapColSize; j++) {
				iceMap[i][j] = str.charAt(j) - '0'; //Char to Int 
			}
		}
			
		
		int totalIceCream = 0; 
		
		for(int i = 0; i < mapRowSize; i++)
			for(int j = 0; j < mapColSize; j++) {
				if(iceMap[i][j] == hole) {
					bfs(iceMap, i, j);
					totalIceCream++; 
				}
			}
		
		System.out.println(totalIceCream);
	}

}

구현방식2) DFS(깊이 우선 탐색)를 사용해 연결된 좌표에 대해 최대한 깊게 들어가 확인하기 

main 메서드 내에서 이중for문으로 모든 좌표 위치에 대해 DFS를 수행한다. 

dfs 함수 내에서 좌표 값이 hole(구멍이 뚫린 경우)인 경우 -> 해당 위치 방문 처리 -> 상하좌우에 대해 재귀함수 호출  

import java.util.Scanner;

public class Main {

	public static int mapRowSize, mapColSize;
	
	public static int hole = 0, wall = 1, visited = 2;
	
	public static boolean dfs(int iceMap[][], int vertexRow, int vertexCol) {
		//Map의 좌표 범위 체크 
		if(vertexRow <= -1 || vertexRow >= mapRowSize || vertexCol <= -1 || vertexCol >= mapColSize)
			return false;
		
		if(iceMap[vertexRow][vertexCol] == hole) {
			//해당 노드 방문 처리
			iceMap[vertexRow][vertexCol] = visited;
			//상하좌우 좌표에 대해 재귀적 호출 
			dfs(iceMap, vertexRow-1, vertexCol);
			dfs(iceMap, vertexRow+1, vertexCol);
			dfs(iceMap, vertexRow, vertexCol-1);
			dfs(iceMap, vertexRow, vertexCol+1);
			return true; 
		}
		
		return false; 
	}
	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		
		mapRowSize = kbd.nextInt();
		mapColSize = kbd.nextInt();
		kbd.nextLine(); //버퍼 지우기 
		
		int iceMap[][] = new int[mapRowSize][mapColSize]; //그래프의 경우 -> 인접행렬이라고 생각하기 
		
		/* 2차원 리스트의 맵 정보 입력 받기 */
		for(int i = 0; i < mapRowSize; i++) {
			String str = kbd.nextLine(); //문자열로 입력받기 
			for(int j = 0; j < mapColSize; j++) {
				iceMap[i][j] = str.charAt(j) - '0'; //Char to Int 
			}
		}
			
		int totalIceCream = 0; 
		
		for(int i = 0; i < mapRowSize; i++)
			for(int j = 0; j < mapColSize; j++) {
				//현재 위치에서 DFS 수행
				if(dfs(iceMap, i, j))
					 totalIceCream += 1;
			}
		
		System.out.println(totalIceCream);

	}
}

 

개선할 부분

Q. Queue에 원소 값 2개를 저장할 수 없나? BFS 구현 시 row와 col 각각에 대해 2개의 큐 선언해서 저장했는데,  한 번에 저장할 방법을 찾아보자!

방식1) Pair 역할을 담당할 새로운 클래스 생성하기

주어진 좌표에 대해 Pair 클래스 객체 생성 -> 해당 객체를 Queue에 넣어주기 

//나머지 부분은 위에서 작성한 코드와 동일함 
//추가하고(Pair 클래스) 변경한(bfs함수) 코드 부분만 첨부함 

class Pair{
	public int row;
	public int col;
	
	Pair(int row, int col){
		this.row = row;
		this.col = col;
	}
}

public static void bfs(int iceMap[][], int startVertexRow, int startVertexCol) { 
		Queue<Pair> queue = new LinkedList<Pair>();
		
		Pair pair = new Pair(startVertexRow, startVertexCol);
		
		queue.offer(pair);
		iceMap[startVertexRow][startVertexCol] = visited; 
		
		while(!queue.isEmpty()) {
			Pair dequeueVal = queue.poll();
			startVertexRow = dequeueVal.row; 
			startVertexCol = dequeueVal.col;
			
			for(int i = 0; i < dx.length; i++) {
				int x = startVertexRow + dx[i]; //row -> 헷갈린 부분 : x가 좌표에서의 x값이 아니라 행임! 
				int y = startVertexCol + dy[i]; //col -> y는 열임! 
				
				if(x != -1 && x != mapRowSize && y != -1 && y != mapColSize) { //x좌표 -> col, y좌표 -> row 
					if(iceMap[x][y] == hole) {
						pair = new Pair(x, y);
						queue.offer(pair);
						iceMap[x][y] = visited; 
					}
				}
			}
		}
	}