[백준2178] 미로 탐색

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

2178번: 미로 탐색

 

문제설명

목적지를 향해 미로를 탐색하여 이동할 때 지나야 하는 최소 칸수를 구한다. 

문제 해결 방법

BFS로 풀었다. 

코드 구현

import java.io.BufferedReader;
import java.awt.Point;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;


public class Main {
	public static int N, M;
	public static int[] dx = {-1, 0, 1, 0};
	public static int[] dy = {0, -1, 0, 1};
	public static int[][] graph;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		//1,1에서 출발 
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		graph = new int[N][M];
		
		for(int i = 0; i<N; i++) {
			Arrays.fill(graph[i], 0);
		}
		
		//N, M 위치로 이동
		
		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				graph[i][j] = Character.getNumericValue(str.charAt(j));
			}
		}
		
		bfs();
		System.out.println(graph[N-1][M-1]);
		// BFS 

	}
	
	public static void bfs() {
		Queue<Point> q = new LinkedList<Point>();
		q.add(new Point(0,0));
		while(!q.isEmpty()) {
			Point p = q.poll();
			
			for(int i = 0; i < 4; i++) {
				int x = p.x + dx[i];
				int y = p.y + dy[i];
				if(x<0 || y<0 || x>=N || y>=M) {
					continue;
				}
				if(graph[x][y] == 1) {
					q.add(new Point(x, y));
					graph[x][y]=graph[p.x][p.y]+1;
				}

			}
		}	
	}
}

 

시간/공간 복잡도

O(N^2)

최적화 및 개선

하지않음 

어려웠던 점

좌표를 어떻게 저장해야할까 고민을 많이 하다가 

구글링해서 Point를 사용하여 문제를 해결했다.