[2024.11.07] 가중치가 동일한 그래프에서의 BFS / 최소 경로로 탈출 하기

 

어제 못풀었던 문제를 푸려고 시도하다가, 못풀겠어가지고 다른 문제를 풀었음

치욕적임

내일은 꼭 풀어내겠음...

 

https://www.codetree.ai/missions/2/problems/escape-with-min-distance/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

난이도

• 하

 

실수한 점 & 배운 점

• 최단거리를 구하기 위한 step 2차원 배열에 대해 각 거리를 계산하는 부분을 잘못 설정함.
  같은 크기의 step을 매겨줘야 하는 깊이에 대해서 1씩 증가하게 매겨지도록 로직을 짜놔서 12가 나와야하는데 14가 나오는 등 step이 엉망으로 세어졌음

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

class Vertex{
    int r;
    int c;

    public Vertex(int r, int c){
        this.r = r;
        this.c = c;
    }
}

public class Main {

    static int[] dr = {1, 0, -1, 0};
    static int[] dc = {0, 1, 0, -1};

    static int n;
    static int m;
    static int[][] grid;
    static boolean[][] isVisited;
    static int[][] step;
    static int currNum = 0;
    static int answer = -1;
    static Queue<Vertex> queue;
        
    public static void findWay(int r, int c){
        while(!queue.isEmpty()){
            Vertex curr = queue.poll();
            currNum = step[curr.r][curr.c];
            
            for(int i = 0; i<4; i++){
                int new_r = curr.r + dr[i];
                int new_c = curr.c + dc[i];
                if(canGo(new_r, new_c)){
                    isVisited[new_r][new_c] = true;
                    step[new_r][new_c] = currNum+1;
                    queue.add(new Vertex(new_r, new_c));
                }
            }
        }
    }

    public static boolean isRange(int r, int c){
        return (r>=0 && r<n && c>=0 && c<m);
    }

    public static boolean canGo(int r, int c){
        if(!isRange(r, c)) return false;
        if(grid[r][c]==0 || isVisited[r][c]) return false;
        return true;
    }
    
    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());

        grid = new int[n][m];
        isVisited = new boolean[n][m];
        step = new int[n][m];
        queue = new LinkedList<>();

        for(int i = 0; i<n; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j<m; j++){
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        isVisited[0][0] = true;
        queue.add(new Vertex(0, 0));
        findWay(0, 0);

        if(isVisited[n-1][m-1]) answer = step[n-1][m-1];

        System.out.println(answer);
    }
}