BOJ - 녹색 옷 입은 애가 젤다지? 4485번 (JAVA)

❓ 문제 - 백준 녹색 옷 입은 애가 젤다지? 4485번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/4485)

4485번: 녹색 옷 입은 애가 젤다지?

 

 

📝 문제해결법

1. 이 문제는 다익스트라 풀이로 해결하였다.

• 일단 N이 125라서 DFS, BFS로 완전탐색 나오면 시간초과 발생함 -> 다익스트라로 풀어야함
• 어차피 출발지(0, 0)에서 목적지(n-1, n-1)의 최단 거리를 구하는 문제로 해석되기 때문에 다익스트라로 풂
• 링크는 인접한 4방향(상, 하, 좌, 우)로만 이동할 수 있으므로 다익스트라 구현 시에 인접 4방향만 이동할 수 있도록 구현
• BFS스럽게 visited 방문처리를 해주며, 기존 다익스트라로 푸는 방법 그대로 구현해하고 마지막에 목적지에 distance 값을 답으로 출력해주면 됨

2. 느낀점

• 뭔가 BFS 방법을 다익스트라에 적용시켜 구현할 수 있냐를 묻는 문제 같음...
• 이런 방법으로도 할 수 있구나!

 

💻 소스코드

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

public class Main_4485 {
    public static int n;
    public static int[] dx ={-1, 1, 0, 0};
    public static int[] dy ={0, 0, -1, 1};
    public static int[][] map;
    public static int[][] distance;
    public static boolean[][] visited;
    public static final int INF = (int)1e9;
    public static class Node implements Comparable<Node>{
        int x;
        int y;
        int distance;
        public Node(int x, int y, int distance){
            this.x = x;
            this.y = y;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node o) {
            return this.distance-o.distance;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        StringBuilder sb = new StringBuilder();
        int cnt = 1;
        while (true){
            n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            map = new int[n][n];
            distance = new int[n][n];
            visited = new boolean[n][n];
            for(int i=0;i<n;i++){
                st = new StringTokenizer(br.readLine(), " ");
                for(int j=0;j<n;j++){
                    map[i][j] = Integer.parseInt(st.nextToken());
                    distance[i][j] = INF;
                }
            }

            dijkstra();
            sb.append("Problem ").append(cnt).append(": ").append(distance[n-1][n-1]).append("\n");
            cnt++;


        }

        System.out.println(sb.toString());
    }

    public static void dijkstra(){
        visited[0][0] = true;
        distance[0][0] = map[0][0];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(0, 0, distance[0][0]));
        while (!pq.isEmpty()){
            Node node = pq.poll();
            for(int d=0;d<4;d++){
                int nx = node.x + dx[d];
                int ny = node.y + dy[d];
                if(0<= nx && nx < n && 0 <= ny && ny < n){
                    if(!visited[nx][ny]){
                        int cost = node.distance + map[nx][ny];
                        if(cost < distance[nx][ny]){
                            distance[nx][ny] = cost;
                            visited[nx][ny] = true;
                            pq.offer(new Node(nx, ny, cost));
                        }
                    }
                }
            }
        }
    }
}