[백준/JAVA] 2178 미로 탐색

미로탐색

---

풀이

1. BFS 알고리즘으로 해결하였다.
2. 좌표를 저장하기 위해 Pos라는 객체를 사용하였다.
3. 사방으로 이동 가능한 경우의 수를 고려해서 맨 아래 후기에서 적어둔 연산을 사용하였다.
4. (현재까지 지나온 값) + (다음 지나갈 값) = n + 1 이다.
   자연스레 다음으로 이동할 위치에 현재 위치에 다음 이동할 위치의 값을 더해서 저장하면 된다.
5. 목적지는 N,M 고정이다. 지도의 [N-1,M-1] 의 값을 출력하면 가장 최단거리이다.

---

제출 코드

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

class Main {
    static int[][] map;
    static int M, N;
    static Queue<Pos> q = new LinkedList<>();
    static boolean[][] visited;
    static int[] opsX = {-1, 1, 0, 0};
    static int[] opsY = {0, 0, -1, 1};

    // 좌표를 저장하기 위한 클래스
    static class Pos {
        int x;
        int y;

        Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        // 미로 지도 입력 받기
        map = new int[N][M];
        visited = new boolean[N][M];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < str.length(); j++) {
                map[i][j] = str.charAt(j)-'0';
            }
        }
        bfs(0, 0);
        bw.write(String.valueOf(map[N - 1][M - 1]));
        bw.flush();
    }

    public static void bfs(int x, int y) throws IOException {
        q.add(new Pos(x, y));
        visited[x][y] = true;

        while (!q.isEmpty()) {
            Pos pos = q.poll();

            for (int i = 0; i < 4; i++) {
                int newX = pos.x + opsX[i];
                int newY = pos.y + opsY[i];

                if (0 <= newX && newX < N && 0 <= newY && newY < M){
                    if (map[newX][newY] == 1 && !visited[newX][newY]) {
                        q.offer(new Pos(newX, newY));
                        visited[newX][newY] = true;
                        map[newX][newY] = map[pos.x][pos.y] + 1;
                    }
                }
            }
        }
    }
}

---

입력

4 6
101111
101010
101011
111011

공백 없이 입력 받는다. String을 char 자료형으로 바꿔서 입력받자.

---

연산 과정

1    0    9    10    11    12    
2    0    8    0    12    0    
3    0    7    0    13    14    
4    5    6    0    14    15

지나간 길마다 + 1 씩 계산 되어있다.

---

후기

static int[] opsX = {-1, 1, 0, 0};
static int[] opsY = {0, 0, -1, 1};


for (int i = 0; i < 4; i++) {
    int newX = pos.x + opsX[i];
    int newY = pos.y + opsY[i];

진짜 이 연산 보고 한숨을 푹 쉬었다

몰라서 진짜 노가다 뛰고있었는데....
그냥 외우자

백준 2178 미로 탐색 문제 링크