• 문제링크: https://www.acmicpc.net/problem/2178

설명

• 2차원 배열로 미로를 작성한다.
• Queue를 생성하여 이동할 위치를 저장한다.
  • 시작점을 Queue에 넣는다.
• Queue의 크기가 0이 될때까지 반복한다.
  • Queue에서 poll한다.
  • for문 돌면서 4방향을 탐색한다.
    • 크기를 넘어가는 위치이면, 이동할 수 없다 -> 다른 방향 확인(continue)
    • 이미 방문했거나, 0이라면 -> 다른 방향 확인(continue)
    • 이동할 수 있다면 -> Queue에 넣기, 탐색 시 다음에 밟을 칸에 현재 칸까지의 가중치(여기서는 count가 된다)를 더해주기, 이동했으니 visitied는 true가 된다.

코드

package Algorithm.P2178;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class P2178 { 
	static int N,M;
    static int[][] map;
    static boolean[][] visited;
    
    // 방향
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    
    public static void main(String[] args) throws IOException {
    	System.setIn(new FileInputStream("src/Algorithm/P2178/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        // 미로 생성
        for(int i = 0; i < N; i++){
        	String[] s = br.readLine().split("");
            for(int j =0; j < M; j++){
            	map[i][j] = Integer.parseInt(s[j]);
             }
		}
        
        visited = new boolean[N][M];
        visited[0][0] = true;
        
        bfs(0,0);
        
        System.out.println(map[N-1][M-1]);
	}
    
    public static void bfs(int x, int y){
    	Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        
        while(!q.isEmpty()) {
        	int cur[] = q.poll();
            int curX = cur[0];
            int curY = cur[1];
            
            for(int i = 0; i < 4; i++){
            	int nextX = curX + dx[i];
                int nextY = curY + dy[i];
                
                // map의 범위를 넘어서 갈 수 없음
                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= M)
	                continue;
                    
                // 이미 방문했거나, 0이라서 방문할 수 없음    
				if (visited[nextX][nextY] || map[nextX][nextY] == 0)      
                	continue;
                    
                // 추후 이동할 큐     
				q.add(new int[]{nextX, nextY});
                map[nextX][nextY] = map[curX][curY] + 1;	// 다음에 밟을 칸에 가중치를 둠
                visited[nextX][nextY] = true;
           	}
        }   
	}
}	

아직 BFS가 익숙하지 않다.