[JAVA]백준_2178_미로탐색

문제링크

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

2178번: 미로 탐색

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static int N,M;
	static int map[][];
	static boolean isVisited[][];
	static int result = Integer.MAX_VALUE;
	static Queue<Node> q = new LinkedList<>();
	static int dx[] = {0,0,-1,1};
	static int dy[] = {-1,1,0,0};
	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());
		
		map = new int[N][M];
		isVisited = new boolean[N][M];
		
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			String str = st.nextToken();
			for(int j=0;j<M;j++) map[i][j] = str.charAt(j)-'0';
		}
		
		q.offer(new Node(0,0,1));
		bfs();
		System.out.println(result);
	}
	
	static void bfs() {
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			
			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				
				if(nx<0 || nx>=N || ny<0 || ny>=M || isVisited[nx][ny] || map[nx][ny]==0) continue;
				if(nx == N-1 && ny == M-1) {
					int len = node.weight+1;
					result = Math.min(len, result);
				}
				isVisited[nx][ny] = true;
				q.offer(new Node(nx,ny,node.weight+1));
			}

		}
	}
	
	static class Node{
		int x;
		int y;
		int weight;
		public Node(int x, int y, int weight) {
			super();
			this.x = x;
			this.y = y;
			this.weight = weight;
		}
	}
}

 

위치를 나타내기 위해 클래스를 하나 만들어주었다.

좌표와 길이를 나타내는 Weight를 넣어주었다.

 

bfs 함수이다. 상하좌우를 탐색하면서 큐에 넣어준다.

만약 배열범위를 벗어나거나 방문했던 곳이거나 0이어서 갈 수 없는 길이면 continue를 통해 넘어가준다.

이외의 경우에는 큐에 넣어준다.

만약 nx,ny가 도착지점에 달하면 현재 길이는 node.weight+1이다. 

이전에 이때까지 왔던 길이를 weight 변수에 넣어주었기 때문에 새로 갈 길은 weight +1이기 때문이다.

 

그리고 현재 len과 result중 min 값을 찾아서 result 에 넣어준다.