[알고리즘] 백준 - 2178 ( 미로 탐색 ) / 자바 (BFS)

배고픈메꾸리·2021년 6월 10일
0

알고리즘

목록 보기
92/128
import java.util.*;
import java.io.*;

class Node{
	public int x;
	public int y;
	public int count;
	
	public Node(int x, int y , int count) {
		this.x = x;
		this.y = y;
		this.count = count;
	}

}
class Main {
	static int N , M;
	static int[][] map;
	static boolean[][] check;
	static int[] dx = { 0 , 1 , 0 , -1};
	static int[] dy = { 1 , 0 , -1 , 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+2][M+2];
		check = new boolean[N+2][M+2];
		for(int i = 1 ; i <= N ; i++) {
			String s = br.readLine();
			for(int j =1 ; j <= M ; j++) {
				map[i][j] = s.charAt(j-1)-'0';
			}
		}

		System.out.print(bfs(new Node(1,1,1)));
	}
	
	private static int bfs(Node n) {
		Queue<Node> queue = new LinkedList<>();
		queue.offer(n);
		check[n.x][n.y]= true; 
		while(!queue.isEmpty()) {
			Node node = queue.poll();
			if(node.x == N && node.y ==M) {
				return node.count;
			}
			for(int i = 0 ; i < 4 ; i++) {
				int nextX = node.x + dx[i];
				int nextY = node.y + dy[i];
				if(map[nextX][nextY] ==1 && !check[nextX][nextY]) {
					queue.offer(new Node(nextX , nextY , node.count+1));
					check[nextX][nextY]= true; 
				}
			}
			
		}
		return -1;
		
	}
}

count를 가지고 다니는게 중요하다 전역변수로하면 모든 경로가 다나온다

profile
FE 개발자가 되자

0개의 댓글