[백준]2178 미로탐색

스스로 풀어보려고 하루동안 노력했으나 안돼서 깔끔하게 포기!(이런게 수두룩빽빽이겠지..) 다른 풀이코드를 보고 내가 다시 짜봤다. bfs를 이용하여 풀면 되는 문제이다. 처음엔 dp인가..? 해서 지나는 경로마다 값을 다 저장해두려고 했으나 실패.. 좌표개념 자체를 생각못해서 dfs로 요리조리 이동하면서 풀려고 했는데 그것마저도 잘 안됐다.. 슬프지만 많이 푸는게 답ㅠ!

성공코드는 이렇다.

package baekjoon;

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

public class Main_2178 {
    static int N;
    static int M;
    static int count;

    static int dx[] = {0, 0, -1, 1};    // 좌우이동
    static int dy[] = {-1, 1, 0, 0};    // 상하이동

    static int[][] find;
    static boolean[][] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.valueOf(st.nextToken());    // 줄의 갯수
        M = Integer.valueOf(st.nextToken());    // 칸의 갯수

        find = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                int ss = Integer.valueOf(s.substring(j, j + 1));
                find[i][j] = ss;
            }
        }
        bfs(0,0);
        System.out.println(find[N-1][M-1]);
    }
    public static void bfs(int x, int y) {
        Queue<int[]> q = new LinkedList();
        q.offer(new int[]{x, y});
        while(!q.isEmpty()) {
            int[] now = q.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)
                    continue;
                if (visit[nextX][nextY] || find[nextX][nextY] == 0)
                    continue;

                q.add(new int[] {nextX, nextY});
                find[nextX][nextY] = find[nowX][nowY] + 1;
                visit[nextX][nextY] = true;
            }

        }
    }
}

현재 위치를 큐에 넣어주고 움직일 수 있는 상하좌우의 값을 구해 큐에 추가한다. 인덱스가 넘어가버리거나 이동경로가 아닌경우, 이미 한번 방문했던 경우에는 continue 시켜주고 그 외에는 현재 위치에서 가지고 있는 값에 +1씩 해주며 이동시킨다.
이동 가능한 경로에 최단거리가 아닌 최장거리의 값이 들어있으면 어떻게 하나 의문이 들었는데, 이동가능한 경로를 큐에 다 넣어보기 때문에 제일 빨리 도달하는 경로의 값이 visit 배열에 먼저 세팅되고 오래 걸리는 경로는 이미 방문이력이 있기 때문에 continue 되어 자연스레 최단경로가 차지하게 된다.

실패코드 🤤

package baekjoon;

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

public class Main_2178 {
    static int N;
    static int M;
    static int count;

    static int[][] find;
    static boolean[][] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.valueOf(st.nextToken());    // 줄의 갯수
        M = Integer.valueOf(st.nextToken());    // 칸의 갯수

        find = new int[N + 1][M + 1];
        visit = new boolean[N + 1][M + 1];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < M; j++) {
                int ss = Integer.valueOf(s.substring(j, j + 1));
                find[i][j] = ss;
            }
        }
        move(0,0);
    }
    public static void move(int i, int j) {
        // 위로 이동 i-1, j
        // 아래로 이동 i+1, j
        // 우로 이동 i, j+1
        // 좌로 이동 i, j-1
        if(i==N-1 && j==M-1) {
            visit[i][j]=true;
            System.out.println(i+" "+j+" 끝"+count);
            return;
        }
        if(!visit[N-1][M-1] && !visit[i][j]) {
            System.out.println(i+" "+j+" 무브");
            count++;
            visit[i][j] = true;
            // 우로 이동 가능
            if(j+1<M && find[i][j+1]==1 && !visit[i][j+1]) {
                move(i, j+1);
            }
            // 아래로 이동 가능
            if(i+1<N && find[i+1][j]==1 && !visit[i+1][j]) {
                move(i+1, j);
            }
            // 위로 이동 가능
            if(i-1>-1 && find[i-1][j]==1 && !visit[i-1][j]) {
                move(i-1, j);
            }
            // 좌로 이동 가능
            if(j-1>-1 && find[i][j-1]==1 && !visit[i][j-1]) {
                move(i, j-1);
            }
        } else {
            System.out.println("들렀어 "+i+" "+j);
        }
    }
}