[BAEKJOON] 백준 그래프 2178 :: 미로 탐색

 

💬  문제 설명

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.
이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때
지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.
위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

 

🔨  입출력 예

입력 

• 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다.
• 각각의 수들은 붙어서 입력으로 주어진다.

 

출력

• 첫째 줄에 지나야 하는 최소의 칸 수를 출력한다.
• 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

 

예제 입력 1)

4 6
101111
101010
101011
111011

 

예제 출력 1)

15

 

예제 입력 2)

4 6
110110
110110
111111
111101

 

예제 출력 2)

9

​

예제 입력 3)

2 25
1011101110111011101110111
1110111011101110111011101

 

예제 출력 3)

38

​

예제 입력 4)

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

 

예제 출력 4)

13

​

 

💻  Main.java

• DFS와 BFS 모두 사용가능하지만, DFS를 이용해 풀면 시간초과가 뜬다.
• 나는 DFS로 풀다가 시간초과가 떠서 BFS로 다시 한번 풀어줬다.

BFS_ver

/* 백준 그래프 - 2178 :: 미로 탑색 - BFS*/

import java.util.*;
import java.io.*;

class Point { 
	public int x, y; 
	Point (int x, int y){ 
		this.x = x; 
		this.y = y; 
	} 
}
	
public class Main {
	static int[][] board, dis;
	static int n, m;
	// 인접한 칸(좌우 위 아래) 좌표 정보
	static int[] dx = {-1, 0, 1, 0}; 
	static int[] dy = {0, 1, 0, -1};

	static public void BFS(int x, int y) { 
		Queue<Point> Q = new LinkedList<>();
		Q.offer(new Point(x, y)); 
		board[x][y] = 1; 
		
        //큐가 다 떨어질때까지 반복
		while(!Q.isEmpty()) { 
			Point tmp = Q.poll(); 
			for(int i = 0; i < 4; i++) { 
				int nx = tmp.x + dx[i]; 
				int ny = tmp.y + dy[i]; 
				
				// 경계선 검사 
				if(nx >= 0 && nx <= n - 1 && ny >= 0 && ny <= m - 1 && board[nx][ny] == 1) {
					board[nx][ny] = 0; 
					Q.offer(new Point(nx, ny));
                    // 원래 거리에서 + 1
					dis[nx][ny] = dis[tmp.x][tmp.y] + 1; 
				}
			}
		}
	}

		
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		board = new int[n][m];
		dis = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			char[] cList = br.readLine().toCharArray();
			for(int j = 0; j < m; j++) {
				board[i][j] = cList[j] - '0';
			}
		}
		
		BFS(0, 0);
		System.out.println(dis[n-1][m-1] + 1);
		
		br.close();
		return ;
	}
}

 

DFS_ver

/* 백준 그래프 - 2178 :: 미로 탑색 - DFS */

import java.util.*;
import java.io.*;

public class Main {
	static int[][] board;
	static int cnt = 1;
	static int min = Integer.MAX_VALUE;
	
	// 인접한 칸(좌우 위 아래) 좌표 정보
	static int[] dx = {-1, 0, 1, 0};
	static int[] dy = {0, 1, 0, -1};
	
	static void DFS(int x, int y, int n, int m) {
		if(x == n - 1 && y == m - 1)
			min = Math.min(min, cnt);
		else {
			for(int i = 0; i < 4; i++) { 
				// 다음에 올 좌표
				int nx = x + dx[i]; 
				int ny = y + dy[i]; 
				
				// 지표 경계 값 검사
				if(nx >= 0 && ny >= 0 && nx < n && ny < m && board[nx][ny] == 1) { 
					cnt++;
					board[nx][ny] = 0;
					DFS(nx, ny, n, m); 
					cnt--;
					board[nx][ny] = 1;
				}
			}
		}
	}
		
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		board = new int[n][m];
		
		for(int i = 0; i < n; i++) {
			char[] cList = br.readLine().toCharArray();
			for(int j = 0; j < m; j++) {
				board[i][j] = cList[j] - '0';
			}
		}
		
		DFS(0, 0, n, m);
		System.out.println(min);
		
		br.close();
		return ;
	}
}