[백준(Baekjoon)][자바(java)] 2178 : 미로 탐색 / DFS와 BFS

 

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {

	static int n, m, maze[][];
	static int dx[] = { 1, 0, -1, 0 };
	static int dy[] = { 0, 1, 0, -1 };
	static final int wall = 0, path = 1, path_v = 2;
	
	static class Cell {
		int x;
		int y;
		int d;  // the shortest distance
		public Cell( int x, int y, int d ) {
			this.x = x;
			this.y = y;
			this.d = d;
		}
	}
	
	public static int findPath_BFS( int x, int y ) {
		Deque<Cell> q = new ArrayDeque<>();
		q.add( new Cell( x, y, 1 ) );
		maze[x][y] = path_v;
		while( !q.isEmpty() ) {
			Cell c = q.remove();
			if( c.x == n && c.y == m )
				return c.d;
			for( int u = 0; u < 4; u++ ) {  // top,bottom,left,right
	            int x_p = c.x + dx[u];  // path x
	            int y_p = c.y + dy[u];  // path y
	            if( 1 <= x_p && x_p <= n && 1 <= y_p && y_p <= m && maze[x_p][y_p] == path ) {
	            	q.add( new Cell( x_p, y_p, c.d+1 ) );
	            	maze[x_p][y_p] = path_v;
	            }    
	        }
		}
		return -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() );
		int i, j;
		maze = new int[n+1][m+1];
		for( i = 1; i <= n; i++ ) {
			String s = br.readLine();
			for( j = 1; j <= m; j++ )
				maze[i][j] = s.charAt(j-1) - '0';
		}
		br.close();
		
		System.out.println( findPath_BFS( 1, 1 ) );

	}
}