[DFS/BFS] 문제 이름 : 미로 탈출

문제 설명

N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 

 

1. 사용 알고리즘

그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 

 

2. 문제 해결 아이디어

주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수는 차감해줘야 한다. 이를 위해 주어진 2차원 배열의 원소값을 이동 횟수라는 가중치라고 하면, 새로 방문한 노드의 가중치 = 이전 노드의 가중치 + 1로 업데이트 시켜준다. 그러면 노드들을 탐색하며 목표 지점까지의 이동한 최소 칸의 개수를 구할 수 있다. 

 

3. 코드

공통) 이동 가능한 모든 노드를 탐색해 시작 지점부터 해당 노드까지의 칸 이동 횟수 저장 -> 깊이 우선으로 탐색하느냐, 너비 우선으로 탐색하느냐의 차이 

구현방식1) BFS

bfs() 메서드 동작 흐름 : BFS 알고리즘을 사용해 이동 가능한(괴물이 없는 부분) 모든 노드들을 탐색하며 가중치 증가시키기 -> 최종 목표 지점인 (N,M)의 원소값 반환(해당 지점 도달을 위해 이동한 칸의 최소 개수) 

-> Node 클래스 생성하여 Queue에 Node 객체 enqueue(2차원 배열에서의 위치 row&col 동시 저장) 

-> 주인공이 이동한 가능한 거리에 대한 dx[], dy[] 리스트 생성하여 for문으로 이동 확인 

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

class Node{
	private int x;
	private int y;
	
	public Node(int x, int y) {
		this.x = x;
		this.y = y; 
	}
	
	public int getX() {
		return this.x;
	}
	
	public int getY() {
		return this.y;
	}
}

public class Main {

	public static int rowSize, colSize;
	public static int map[][];
	
	/*이동할 4가지 방향 정의*/
	public static int dx[] = {-1, 0, 1, 0}; //북 동 남 서
	public static int dy[] = {0, 1, 0, -1}; 
	
	public static int monster = 0, safe = 1;
	
	public static int bfs(int x, int y) { //x - row, y - col
		Queue<Node> q = new LinkedList<>(); 
		q.offer(new Node(x, y)); //Node 객체 생성 & enqueue 한번에 하기(코드 줄이기) 
		
		//빈 큐일때까지 반복 
		while(!q.isEmpty()) {
			Node node = q.poll();
			x = node.getX(); //현재 위치 재설정 
			y = node.getY(); 
			
			//현재 위치에서 4가지 방향으로의 위치 확인
			for(int i = 0; i < dx.length; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				//해당 위치의 원소값이 조건을 만족하는지 확인
				//1. 미로 공간 벗어난 경우
				if(nx < 0 || nx >= rowSize || ny < 0 || ny >= colSize) continue; 
				//2. 몬스터가 있는 경우 
				if(map[nx][ny] == monster) continue; 
				//3. 해당 노드를 처음 방문하는 경우 
				if(map[nx][ny] == safe) {
					map[nx][ny] = map[x][y] + 1; //이동 횟수에 대한 가중치 값(원소값) 증가 
					q.offer(new Node(nx, ny));
					
				}
			}
		}
		
		//최종 위치의 이동 횟수에 대한 가중치 반환(최단거리 반환) 
		return map[rowSize-1][colSize-1];
	}

	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);

		rowSize = kbd.nextInt();
		colSize = kbd.nextInt();
		kbd.nextLine();
		
		//2차원 배열 MAP 원소값 입력 
		map = new int[rowSize][colSize];
		for(int i = 0; i < rowSize; i++) {
			String str = kbd.nextLine();
			for(int j = 0; j < colSize; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		
		//BFS 수행 결과 출력 
		System.out.println(bfs(0,0)); 
	}

}

구현방식2) DFS

dfs() 메서드 동작 흐름 : 위에서 설명한 bfs()와 동일함

import java.util.*;

public class Main {

	public static int rowSize, colSize;
	public static int map[][];
	
	/*이동할 4가지 방향 정의*/
	public static int dx[] = {-1, 0, 1, 0}; //북 동 남 서
	public static int dy[] = {0, 1, 0, -1}; 
	
	public static int monster = 0, safe = 1;
	
	public static void dfs(int x, int y) {
		for(int i = 0; i < dx.length; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			if(nx < 0 || nx > rowSize-1 || ny < 0 || ny > colSize-1) continue;
			if(map[nx][ny] == monster) continue;
			if(map[nx][ny] == safe) {
				map[nx][ny] = map[x][y] + 1;
				dfs(nx, ny);
			}
		}
	}

	
	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);

		rowSize = kbd.nextInt();
		colSize = kbd.nextInt();
		kbd.nextLine();
		
		//2차원 배열 MAP 원소값 입력 
		map = new int[rowSize][colSize];
		for(int i = 0; i < rowSize; i++) {
			String str = kbd.nextLine();
			for(int j = 0; j < colSize; j++) {
				map[i][j] = str.charAt(j) - '0';
			}
		}
		
		dfs(0,0); 
		System.out.println(map[rowSize-1][colSize-1]); 
	}

}