[백준 알고리즘 - 2178] 미로찾기(bfs) - java

푼지 한참 되긴 했는데, 방학도 되었고 알고리즘 좀 제대로 복습하고 싶어서 차근차근 기록!

dfs/bfs 중요한 것도 알고 2학년 때 진짜 열심히 했는데.. 그리고 나름 좀 잘했던거 같은데..
시간은 약이 아니라 지우개였다 리셋~ 

---

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

---

그나마 최단 경로 -> bfs 이건 딱 생각나서 생각보단 금방 풀 수 있었다


BFS의 기본 전략
- Vertex v 방문
- v와 인접한 vertex 체크 후 Queue에 삽입

- Queue 사용

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {


   public static void main(String[] args) {
      // TODO Auto-generated method stub
        Scanner scan=new Scanner(System.in);
          
          int N=scan.nextInt(); int M=scan.nextInt();
          int[][] matrix=new int[N][M]; //미로를 담을 2차원 배열 생성
       
          Vertex[][] vertex=new Vertex[N][M];
          for(int i=0; i<N; i++)
        	  for(int j=0; j<M; j++) {
        		  vertex[i][j]=new Vertex();
        		  vertex[i][j].dist=N*M; //모든 Vertex를 생성, dist는 최댓값으로 초기회
        	  }

          
          scan.nextLine();
          for(int i=0; i<N; i++){
            String line=scan.nextLine();//입력 한줄씩 하고
            for(int j=0; j<M; j++){
              matrix[i][j]=Integer.parseInt(line.substring(j,j+1));// 미로 배열에 넣음
              vertex[i][j].x=i; vertex[i][j].y=j;//vertex 각각도 초기화
            }
          }
          


          Queue<Vertex> queue=new LinkedList<Vertex>();//넓이 우선 탐색 수행하기 위한 큐 
          vertex[0][0].dist=1;//시작지점은 거리 1
          queue.add(vertex[0][0]);//(0,0)부터 탐색 시작 -> 큐에 삽입

          
          while(queue.peek()!=null) {
        	//더이상 방문할 노드가 없다면
        	if(queue.peek()==null) break;
        	
          	if(queue.peek().visited==true) {
          		//이미 방문한 노드라면 넘어감
          		queue.poll();
          		continue;
          	}
          	else {
          		//처음 방문했다면 방문 체크하고 연산 수행
          		queue.peek().visited=true;	
          	}

          	int nx=queue.peek().x; int ny=queue.peek().y;
          	//위쪽 길 존재
          	if(nx!=0 && matrix[nx-1][ny]==1) {
          		if(vertex[nx-1][ny].dist>queue.peek().dist+1) 
          			vertex[nx-1][ny].dist=queue.peek().dist+1;
          		queue.add(vertex[nx-1][ny]);
          		
          	}
          	//오른쪽 길 존재
          	if(ny!=M-1 && matrix[nx][ny+1]==1) {
          		if(vertex[nx][ny+1].dist>queue.peek().dist+1)
          			vertex[nx][ny+1].dist=queue.peek().dist+1;
          		queue.add(vertex[nx][ny+1]);
          	}
          	//왼쪽 길 존재
          	if(ny!=0 && matrix[nx][ny-1]==1) {
          		if(vertex[nx][ny-1].dist>queue.peek().dist+1)
          			vertex[nx][ny-1].dist=queue.peek().dist+1;
          		queue.add(vertex[nx][ny-1]);
          	}
          	//아래쪽 길 존재
          	if(nx!=N-1 && matrix[nx+1][ny]==1) 
          	{
          		if(vertex[nx+1][ny].dist>queue.peek().dist+1)
          			vertex[nx+1][ny].dist=queue.peek().dist+1;
          		queue.add(vertex[nx+1][ny]);
          	}
          	queue.poll();
          }
          
          System.out.println(vertex[N-1][M-1].dist);
          
          
     }
       

   

}

class Vertex{
   //초기 인덱스 
    int x=-1; int y=-1;
    //연결 Vertex
    LinkedList<Vertex> linkedList=new LinkedList<Vertex>();
    int dist=-1;
    
    boolean visited=false;//방문 여부를 알기 위한 visted 변수
    
  }