[백준] 2178 문제 - 미로탐색(Java) BufferedReader 사용 풀이 방법

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

이 문제는 (1,1) 위치에서 (N,M) 위치로 가는데 최소 칸수를 구하는 문제이다.

 

최단 경로 문제는 BFS 를 사용하면 된다고 생각하면 된다.  BFS는 갈 수 있는 인접한 경로를 모두 방문하기 때문에 최초 방문된 시점이 출발 노드점에서 갈 수 있는 가장 빠른 경로이기 때문이다. 그래서 이문제도 BFS로 풀면 된다. 최단경로 문제는 BFS로 푼다는 걸 공식처럼 생각하면 된다.

 

시간 복잡도는 인접 행렬을 사용할거기 때문에 N, M의 최댓값이 100이어서 100 * 100 = 10000이다.

 

이 문제는 살짝 까다로운 부분이 입력 부분인데 보통 입력의 각 수들을 공백 단위로 띄워서 주지만 이 문제는 붙여서 준다. 그래서 문제 입력 설명 부분에서 붙여서를 진하게 표시한 것 같다. 

 

직면한 문제와 풀이 방법

문자열로 붙여서 나온 각 수 들을 어떻게 떨어뜨릴지에 대한 문제를 직면했다.

for (int y = 0; y < mapYSize; y++) {
    st = new StringTokenizer(br.readLine());
    String inputStr = st.nextToken();

    for (int x = 0; x < mapXSize; x++) {
        map[y][x] = inputStr.charAt(x) - '0';
    }
}

BufferedReader와 StringTokenizer() 를 이용하여 각 붙여준 수를 String으로 받아서 각 String 한자리 한자리 마다 char() -'0' 를 이용해서 숫자로 변환 후 배열에 담아 풀었다.

 

전체 풀이 코드

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

//https://www.acmicpc.net/problem/2178
public class 미로탐색 {
    /**
     * 1. 아이디어
     * - (1,1)위치에서 (N,M)위치로가는 최소의 칸 수 구하기
     * -
     * <p>
     * 2. 시간 복잡도
     * - 100 * 100 = 10000
     * <p>
     * 3. 변수
     * - 미로 : map[mapYSize][mapXSize]
     * - 방문체크 : isVisited[mapYSize][mapXsize]
     * - 방문 : dx[]{0, 1, 0, -1}, dy[]{-1, 0, 1, 0}
     */

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int[][] map;
    static int mapXSize, mapYSize;
    static boolean[][] isVisited;
    static final int[] dy = new int[]{1, 0, -1, 0};
    static final int[] dx = new int[]{0, 1, 0, -1};

    private static void input() throws IOException {
        st = new StringTokenizer(br.readLine());
        mapYSize = Integer.parseInt(st.nextToken());
        mapXSize = Integer.parseInt(st.nextToken());

        map = new int[mapYSize][mapXSize];
        isVisited = new boolean[mapYSize][mapXSize];

        for (int y = 0; y < mapYSize; y++) {
            st = new StringTokenizer(br.readLine());
            String inputStr = st.nextToken();

            for (int x = 0; x < mapXSize; x++) {
                map[y][x] = inputStr.charAt(x) - '0';
            }
        }
    }

    public static void main(String[] args) throws IOException {
        input();

        solve();

        print();
    }

    private static void print() {
        System.out.print(map[mapYSize - 1][mapXSize - 1]);
    }

    private static void solve() {
        isVisited[0][0] = true;
        bfs(0, 0);
    }

    private static void bfs(int mapY, int intX) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{mapY, intX});

        while (!queue.isEmpty()) {
            int[] curXY = queue.poll();

            for (int i = 0; i < dx.length; i++) {
                int qy = dy[i] + curXY[0];
                int qx = dx[i] + curXY[1];
                int curMin = map[curXY[0]][curXY[1]];

                if (0 <= qx && qx < mapXSize && 0 <= qy && qy < mapYSize && map[qy][qx] == 1 && !isVisited[qy][qx]) {
                    map[qy][qx] = curMin + 1;
                    isVisited[qy][qx] = true;
                    queue.add(new int[]{qy, qx});
                }
            }
        }
    }
}