[백준] 2178번 미로탐색

 

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

2178번: 미로 탐색

---

지난번에 이어 탐색문제에 도전했다!!

호기롭게 dfs로 풀었지만....실패 (시간초과 💢)

 

[DFS 실패한 코드]

import java.util.Scanner;
public class Main {
	
	static int N, M, min = Integer.MAX_VALUE;
	static int[][] miro;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) {
		
		//입력받은 값 변수에 저장 
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N][M];
		miro = new int[N][M];
		for(int i = 0; i < N; i++) {
			String inputStr = sc.next();
			for(int j = 0; j < M; j++) {
				miro[i][j] = inputStr.charAt(j) - '0';
			}
		}
		
		//미로탐색 시작 
		visited[0][0] = true;
		searchMiro(0, 0, 1);
		System.out.println(min);
		
	}
	
    public static void searchMiro(int x, int y, int cnt) {
		
		if(x == N - 1 && y == M - 1) {  //도착위치에 왔을 경우 탐색 종료 
			min = Math.min(min, cnt);
			return;
		}
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			
			//범위를 벗어나거나, 이미 방문했거나, 갈 수 없는 길 일 경우 다음 방향으로 넘어감 
			if(nx < 0 || nx >= N || ny < 0 || ny >= M || visited[nx][ny] || miro[nx][ny] == 0) continue;
		
			visited[nx][ny] = true;
			searchMiro(nx, ny, cnt + 1);
			visited[nx][ny] = false;
				
		}
		
	}

}

 

dfs는 경우의 수를 전체를 확인해야 답을 찾을 수 있는 문제에 적합하다.

 

이 풀이로 예시 테스트케이스는 통과했지만

경우의 수를 모두 확인하기 때문에

경우의 수가 많은 경우 시간초과가 뜬 것 같다

 

TOPCODER 알고리즘 트레이닝

 

bfs는 어느 정도 근처에 구하고 싶은 해가 존재하는 것을 알고 있는 경우에 적합하다고 한다!!

이유로는 시작과 가까운 위치부터 순차적으로 탐색하기 때문일 것으로 예상된다

(확신을 갖기 위해 이 부분을 자세히 공부해봐야겠군,,)

---

[풀이 방법]

1. 입력받은 값 각 변수에 저장 (visited는 방문여부-> true: 방문함 / false: 방문안함, miro는 미로의 경로 및 현재 위치까지 이동한 칸 수를 의미)

2. 첫 번째 위치(0, 0)을 방문표시 true로 변경

3. 첫 번째 위치(0, 0) 큐에 추가

4. 다음과 같은 과정을 큐가 비어질때까지 반복

   4-1) 값을 꺼낸다. (큐 자료구조를 사용했으므로 큐에 있는 위치들 중 가장 마지막에 추가한 위치가 나옴)

   4-2) 상하좌우 4가지 방향으로 이동을 시도

           이때, 다음 위치가 범위를 벗어났거나 이미 방문했거나 갈 수 없는 길 일 경우 가지 않고 다음 방향으로 이동을 시도

   4-3) 이동 할 위치 visited에 방문표시 true로 변경

   4-4) 이동 할 위치 miro에 현재까지 이동한 칸 수 + 1을 해줌

   4-5) 이동 할 위치 큐에 추가

5. miro의 도착위치에 저장되어 있는 정수를 출력

 

[코드_Java]

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


class Dot{
	int x, y;
	Dot(int x, int y) {this.x = x; this.y = y;}
}

public class Main {
	
	static int N, M;
	static int[][] miro;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	public static void main(String[] args) {
		
		//입력받은 값 변수에 저장 
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		visited = new boolean[N][M];
		miro = new int[N][M];
		for(int i = 0; i < N; i++) {
			String inputStr = sc.next();
			for(int j = 0; j < M; j++) {
				miro[i][j] = inputStr.charAt(j) - '0';
			}
		}
		
		bfs();
		System.out.println(miro[N - 1][M - 1]);
		
	}
	
	public static void bfs() {
		
		Queue<Dot> q = new LinkedList<>();
		
		visited[0][0] = true;
		q.add(new Dot(0, 0));
		while(!q.isEmpty()) {
			Dot cul = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int nextX = cul.x + dx[i];
				int nextY = cul.y + dy[i];
				
				//범위를 벗어났거나, 이미 방문했거나, 갈 수 없는 길인 경우 다음 방향으로 이동 
				if(nextX < 0 || nextX >= N || nextY < 0 || nextY >= M || visited[nextX][nextY] || miro[nextX][nextY] == 0) continue;
				
			    visited[nextX][nextY] = true;                
			    miro[nextX][nextY] = miro[cul.x][cul.y] + 1;   //해당 위치에 올때까지 지나온 칸 수 저장 
			    q.add(new Dot(nextX, nextY));                
			}
		}
		
	}