[백준/BOJ/JAVA] 2178 미로 탐색

 

 

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제

 

 

bfs로 푸는 문제다.. 아니 사실 모르겠다.. dfs도 되나?

길을 찾아가며 +1씩 카운팅 해주고, map[N-1][M-1]을 출력해주면 된다.

 

 

main

visited = new boolean[N][M];
visited[0][0] = true;
bfs(0, 0);
System.out.println(map[N-1][M-1]);

출발점인 (1, 1) 지점에 방문표시를 하고, bfs를 돌려준다.

 

 

bfs

public static void bfs(int x, int y) {
    Queue<int[]> que = new LinkedList<>();
    que.add(new int[] {x,y});

    while(!que.isEmpty()) {
        int[] now = que.poll();
        int nowX = now[0];
        int nowY = now[1];

        for(int i=0; i<4; i++) {
            int nextX = nowX + dx[i];
            int nextY = nowY + dy[i];

            if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                if(map[nextX][nextY]==1 && !visited[nextX][nextY]){
                    que.add(new int[] {nextX,nextY});
                    map[nextX][nextY] = map[nowX][nowY] + 1;
                    visited[nextX][nextY] = true;
                }
            }
        }
    }
}

+1 해주면 끝~!

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class BOJ_2178 {
    static final int[] dx= {0,0,1,-1};
    static final int[] dy = {1,-1,0,0};
    static int N;
    static int M;
    static boolean[][] visited;
    static int[][] map;
 
    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());
 
        map = new int[N][M];
        for(int i=0; i<N; i++) {
            String s = br.readLine();
            for(int j=0; j<M; j++) {
                map[i][j] = s.charAt(j) - '0';
            }
        }
 
        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[]> que = new LinkedList<>();
        que.add(new int[] {x,y});
 
        while(!que.isEmpty()) {
            int[] now = que.poll();
            int nowX = now[0];
            int nowY = now[1];
 
            for(int i=0; i<4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];
 
                if(nextX>=0 && nextY>=0 && nextX<N && nextY<M){
                    if(map[nextX][nextY]==1 && !visited[nextX][nextY]){
                        que.add(new int[] {nextX,nextY});
                        map[nextX][nextY] = map[nowX][nowY] + 1;
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }
}
 

생각보다 별 거 없는 문제..그러니까 나한테는 별 거 있었다는 말이다.