[백준 알고리즘 - 1261] 알고스팟 (java, BFS)

가중치가 있는 그래프 문제라고 할 수 있다. 

일반적으로 가중치가 있는 그래프 문제는 BFS로 풀 수 없지만

0과 1로만 구성되어있는 경우에는 예외적으로 BFS로 해결이 가능하다.

0인 곳으로 이동할 때는 dist를 증가시켜주지 않고, 1인곳으로 이동할 때는 dist를 증가시켜 주는데

두 vertex를 구분짓기 위해 DEQ를 사용하였다

무조건 나중에 삽입한 vertex를 사용한다고 정한다면 0인 곳은 Last에 삽입하고 

1인 곳은 First에 삽입함으로써 0인 곳을 먼저 방문하도록 설정할 수 있다 

0인 곳을 모두 방문하였다면 별도의 설정 없이도 다음 1인 곳을 탐색하게 된다

상태 저장 변수는 check와 dist를 활용하였다.

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

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String size= br.readLine();
		
		StringTokenizer stringTokenizer=new StringTokenizer(size);
		
		int M=Integer.parseInt(stringTokenizer.nextToken());//가로의 길이(열의 수)
		int N=Integer.parseInt(stringTokenizer.nextToken());//세로의 길이(행의 수)
		
		int[][] maze=new int[N][M];
		int[][] dist=new int[N][M];
		boolean[][] check=new boolean[N][M];
		
		int[] dx= {0,1, 0,-1};//수직이동(행 증감)
		int[] dy= {1,0,-1,-0};//수평이동(열 증감)
		
		for(int i=0;i< N; i++) {
			String input=br.readLine();
			for(int j=0; j<M; j++) {
				maze[i][j]=input.charAt(j)-'0';
			}
		}
		
		Deque<Node> queue=new LinkedList<>();
		queue.addLast(new Node(0,0));
		check[0][0]=true;
		
		
		while(!queue.isEmpty()) {
			Node now=queue.pollLast();
			int x=now.x;
			int y=now.y;
			
			for(int i=0; i<4; i++) {
				int next_x=x+dx[i];
				int next_y=y+dy[i];
				
				if(next_x<0 || next_y <0 || next_x>=N || next_y>=M || check[next_x][next_y])
					continue;
				if(maze[next_x][next_y]==0) {
					dist[next_x][next_y]=dist[x][y];
					queue.addLast(new Node(next_x, next_y));
				}else {
					dist[next_x][next_y]=dist[x][y]+1;
					queue.addFirst(new Node(next_x, next_y));
				}
				check[next_x][next_y]=true;
			
			}
		}
		System.out.println(dist[N-1][M-1]);
	}

}