[백준] 2178번 미로 탐색하기 - JAVA

 
 

 
 
✍️풀이방식 
 
 
1. 문제 분석 
 
 
미로의 각 칸에 들어 있는 숫자 중 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸. 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 이동할 수 있다. 이동한 칸을 셀 때는 시작 위치와 도착 위치를 포함한다.
 
즉 (1,1)에서 (4,6)으로 이동하려면 총 15칸을 지나가야한다. 
 
 
2. 풀이 과정 
 
현재 N,M의 범위가 2이상 100이하로 작기 때문에 시간 복잡도는 따로 고려하지 않아도 된다. 
 
지나야하는 칸 수의 최솟값을 찾는 것은 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지를 구하는 것과 동일. 따라서 BFS를 사용해 최초로 도달했을 때 깊이를 출력하면 문제를 해결할 수 있다. 
 
 
 
 
 

---

 
 
 
🖥️문제풀이
 
 
방향 벡터 정의 

static int[] dx = {0, 1, 0, -1}; // 행(위,아래 이동)
static int[] dy = {1, 0, -1, 0}; // 열(좌,우 이동)

   (i-1, j)   ← 위
(i, j-1) (i,j) (i, j+1)  ← 왼쪽, 현재, 오른쪽
   (i+1, j)   ← 아래

 

• 오른쪽: (0, +1) → 행은 그대로(0), 열만 +1 증가
• 아래: (+1, 0) → 행만 +1 증가, 열은 그대로
• 왼쪽: (0, -1) → 행은 그대로, 열만 -1 감소
• 위: (-1, 0) → 행만 -1 감소, 열은 그대로

 
 

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

public class Main {
	
    static int[] dx={0,1,0,-1}; //상하좌우 탐색
    static int[] dy={1,0,-1,0}; 
    static boolean[][] visited; // 방문 배열  
    static int[][] A; // 데이터 저장 배열 
    static int N,M; 
    
	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());
	    A = new int[N][M];
	    visited = new boolean[N][M]; 
	    
	    for(int i=0;i<N;i++){
	        st=new StringTokenizer(br.readLine());
	        String line =st.nextToken(); //공백이 없기 때문에 일단 한줄로 받기 
	        for(int j=0;j<M;j++){
	            A[i][j] = Integer.parseInt(line.substring(j,j+1)); //한줄로 받은 걸 한칸씩 끊어서입력받기  
	            
	        }
	    }
	    
	    BFS(0,0); 
	    System.out.println(A[N-1][M-1]); 
		
	}
	
	private static void BFS(int i, int j){
	    
	   Queue<int[]>queue = new LinkedList<>(); 
	   queue.offer(new int[] {i,j});  // 시작 노드삽입하기 
	   visited[i][j] = true; 
	   	       
	   while(!queue.isEmpty()){
	       int now[] = queue.poll(); //큐에서 노드 데이터 가져오기 
	       for(int k=0; k<4; k++){ // 상하좌우로 탐색 
	           int x= now[0] + dx[k]; 
	           int y= now[1] + dy[k]; 
	           if(x>=0 && y>=0 && x<N && y<M){ // 배열을 넘어가면 안되고
	               if(A[x][y]!=0&&!visited[x][y]){// 0이여서 갈 수 없거나 방문한 곳이면 안됨
	                visited[x][y] = true;    
	                A[x][y] = A[now[0]][now[1]] +1; 
	                queue.add(new int[] {x,y} );
	               }
	         
	           }
	       }
	       
	   }
	    
	}
	
}

 
 
 

• 출발: (0,0)
• 큐에 [0,0] 넣음
• → 꺼내서 (0,0)에서 오른쪽, 아래 탐색
• → 갈 수 있는 (0,1), (1,0) 큐에 넣음
• 다음에는 (0,1)을 꺼내서 또 상하좌우 탐색 -> 이렇게 퍼져 나가면서 최단 거리 계산된다.