자바(백준) 4485 녹색 옷 입은 애가 젤다지?

오답 노트 & 새로 알게 된 점

이 문제는 가중치가 >= 0 이므로 BFS가 아닌 다익스트라를 이용하였다. 

이차원 배열을 이용하여 시작점에서 도착점까지 최소 비용을 구하는 문제이다.

dist 이차원 배열을 만들어 INF로 초기화하고, 옮기는 곳의 dist와 현재 dist에서 옮기는 곳의 arr값을 비교하여 값을 구한다.

보통 BFS와는 다르게 visit를 사용하지 않는다.

왜?

visit를 사용하면 다음 방문 시에 최솟값이 나올 수 있는데, 그 부분을 놓치게 된다.

 

---

 

코드

package Graph;
 
import java.io.*;
import java.util.*;
 
public class BOJ4485 {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N;
    static int arr[][];
    static int dist[][];
    static final int INF = Integer.MAX_VALUE;
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, 1, -1};
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int test = 1;
        while(true) {
            N = atoi(br.readLine());
 
            if(N == 0) break;
 
            arr = new int[N][N];
            dist = new int[N][N];
 
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    arr[i][j] = atoi(st.nextToken());
                }
            }
            bfs(0, 0);
 
            sb.append("Problem " + test + ": " + dist[N - 1][N - 1]).append("\n");
            test++;
        }
        System.out.print(sb);
    }
 
    static void bfs(int x, int y) {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                dist[i][j] = INF;
            }
        }
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(x);
        q.offer(y);
        dist[x][y] = arr[x][y];
 
        while (!q.isEmpty()) {
            int X = q.poll();
            int Y = q.poll();
            for (int i = 0; i < 4; i++) {
                int dX = X + dx[i];
                int dY = Y + dy[i];
 
                if(!isRangeTrue(dX,dY)) continue;
                if(dist[X][Y] + arr[dX][dY] >= dist[dX][dY]) continue;
 
                dist[dX][dY] = dist[X][Y] + arr[dX][dY];
                q.offer(dX);
                q.offer(dY);
            }
        }
    }
 
    static boolean isRangeTrue(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}