[JAVA] 백준 - 미로 탐색 [2178] (feat. DFS의 문제점)

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

2178번: 미로 탐색

깊이우선탐색(DFS)과 너비우선탐색(BFS) 중에 하나를 선택해서 풀어야 하는 문제였다

시간 복잡도는 비슷하다고 생각해 조금 더 익숙한 DFS를 선택했고, 코드를 작성하였다

코드 설계는 다음과 같이 하였다

1. 우선 사방 중에 갈 수 있는 곳을 찾은 후, 재귀를 이용하여 계속 탐색한다 

2. 더 이상 갈 수 없는 곳이 나오면 해당 함수를 종료(return)하고 다음 방향으로 탐색한다

3. 최종 목적지에 도달하면 전역 변수에 이동한 칸 수를 저장하고, 또다시 백트레킹한 후 탐색한다

4. 이후 탐색하다 또 최종 목적지에 도달하게 되면, 이전 값과 비교하여 더 짧은 거리일 경우 값을 바꿔준다

5. 모든 탐색이 끝난 후, main함수에서 답을 제출한다

import java.util.Scanner;

public class Solution{
	static int[][] block;	//1,0 값 저장
	static int[][] path;	//지나온 길 확인
	static int n,m;
	static int ans;
	static int res = 1;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		
		block = new int[n+1][m+1];
		path = new int[n+1][m+1];
		
		for(int i=0; i<n; i++) {
			String num = sc.next();			
			for(int j=0; j<m; j++) {
				block[i+1][j+1] = num.charAt(j)-'0';
			}
		}
		
        // 결과값 우선 최대값으로 설정
		ans = n*m;
		dfs(1,1);
		System.out.println(ans);
		sc.close();
	}

	public static void dfs(int a, int b) {
    	//최종 목적지 도달할 경우
		if(a==n && b==m) {
			if(res<ans)
				ans = res;
			System.out.println("RES!!!! :"+res);
			return ;
		}
			
		path[a][b] = 1;
		
		//오른쪽
		if(b!=m && block[a][b+1]==1 && path[a][b+1]==0) {
			res++;
			dfs(a,b+1);
			res--;
		}
		
		//아래
		if(a!=n && block[a+1][b]==1 && path[a+1][b]==0) {
			res++;
			dfs(a+1,b);
			res--;
		}
			
		//위
		if(a!=1 && block[a-1][b]==1 && path[a-1][b]==0) {
			res++;
			dfs(a-1,b);
			res--;
		}
		
		//왼쪽
		if(b!=1 && block[a][b-1]==1 && path[a][b-1]==0) {
			res++;
			dfs(a,b-1);
			res--;
		}
	}
}

예제로 주어진 내용들은 모두 성공적으로 결과값을 나타내었다

하지만 코드를 제출하니까 얼마 지나지 않아 답이 틀렸다고 나왔다

사실 코드 이론상으로는 최단 거리를 찾을 수 있으나, 모든 경우를 탐색해야 한다

물론 시간 초과나 메모리 초과 는 나오지 않았지만, 만약 중간에 답을 틀리지 않았다면 언젠간 나왔을 듯 하다

따라서 최단 거리를 구하자 마자 바로 탐색을 종료할 수 있는 BFS로 방법을 바꾸기로 하였다

코드는 다음과 같다

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


public class Solution{
	static int[][] block;
	static int[][] path;
	static int[] dx = {1,-1,0,0};
	static int[] dy = {0,0,1,-1};
	static int n,m;
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		
		block = new int[n+1][m+1];
		path = new int[n+1][m+1];
		
		for(int i=0; i<n; i++) {
			String num = sc.next();			
			for(int j=0; j<m; j++) {
				block[i+1][j+1] = num.charAt(j)-'0';
			}
		}
		bfs(1,1);
		System.out.println(block[n][m]);
		sc.close();
	}
	public static void bfs(int x, int y) {
		Queue<int[]> queue = new LinkedList<>();
		queue.offer(new int[] {x,y});
		
		while(!queue.isEmpty()) {
			int[] point = queue.poll();
			int currentX = point[0];
			int currentY = point[1];
			
			for(int i=0; i<4; i++) {
				int nextX = currentX+dx[i];
				int nextY = currentY+dy[i];
				
				//범위를 벗어난 경우
				if(nextX<1 || nextX>n || nextY<1 || nextY>m)
					continue;
				//길이 아니거나 방문한 경우
				if(block[nextX][nextY]==0 || path[nextX][nextY]==1)
					continue;
				
				queue.add(new int[] {nextX,nextY});
				//해당 점까지 온 경로의 길이를 해당 block에 저장
				block[nextX][nextY] = block[currentX][currentY]+1;	
				path[nextX][nextY] = 1;
			}
		}
		
	}
}

결과는 성공!