[알고리즘] 백준 2178번: BFS

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

2178번: 미로 탐색

 

- 미로 문제의 경우 bfs(Queue) 이용하는 것이 좋다

- 두 개의 값, 여기서는 좌표(1,2)를 set로 묶어서 사용하려면 class를 이용하는 것이 빠르다!

- arr[x][y]에 저장된 값을 q에서 꺼낼 때마다 +1씩 하면, 도착지인 (n,m)에서의 arr[n][m] 값이 최소 칸 수 값이 된다.

 

 

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

public class Main{
	
	static int[][] arr;
	static boolean[][] check;
	static int n,m;
	
	static Queue<Point> q = new LinkedList<>(); //Point class type을 저장
	
	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());
		
		arr = new int[n+1][m+1];
		check = new boolean[n+1][m+1];
		
		for(int i=1; i<=n; i++) {
			String[] lines = br.readLine().split("");
			for(int j=1; j<=m; j++) {
				arr[i][j] = Integer.parseInt(lines[j-1]);
			}
		}
		
		bfs(1,1);
		System.out.println(arr[n][m]);
	}
	
	public static void bfs(int x, int y) {
		
		int[] dx = {1, 0, -1, 0};
		int[] dy = {0, 1, 0, -1};
		
		check[x][y] = true;
		q.add(new Point(x, y));
		
		while(!q.isEmpty()) {
			
			Point now_point = q.remove();
			
			for(int i=0; i<dx.length; i++) {
				int xx = now_point.x + dx[i];
				int yy = now_point.y + dy[i];
						
				if(xx>0 && yy>0 && xx<=n && yy<=m) {
					if(!check[xx][yy] && arr[xx][yy]==1) {
						check[xx][yy] = true;
						arr[xx][yy] = arr[now_point.x][now_point.y] + 1;
						q.add(new Point(xx, yy));
					}
				}
			}
		}
	}
}

class Point{
	int x;
	int y;
	
	Point(int x, int y){
		this.x = x;
		this.y = y;
	}
}