[백준]JAVA - 4485번: 녹색 옷 입은 애가 젤다지?

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

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

🔶 풀이

오랜만에 나온 다익스트라 문제.

 

완전 탐색으로 풀려고 했지만 시간 초과가 발생할 것 같아서 다른 방향을 생각해 봄.

bfs와 다익스트라 알고리즘을 헷갈려하시는 분들이 있는 것 같은데 큰 차이점은 그래프의 가중치 유무와 dp 활용이다.

두 가지 알고리즘 모두 최단 거리를 찾는 알고리즘이지만 그래프의 가중치가 생기면 다익스트라 알고리즘을 사용하는 것이 좋다. 또한, 그래프의 가중치에 음수가 있으면 다익스트라를 사용할 수 없는 점도 기억해 주면 좋다.

 

다익스트라 알고리즘을 처음 접하시는 분은 아래 링크를 참조하면 좋겠다. (https://sookr5416.tistory.com/160)

자바 다익스트라(Dijkstra) 알고리즘 정의 및 작동 원리

다익스트라는 우선순위 큐와 그래프의 가중치를 기록하기 위해서 dp를 활용한다.

public static class Pos implements Comparable<Pos>{
    int x, y, cost;
		
    public Pos (int x, int y, int cost) {
        this.x = x;
        this.y = y;
        this.cost = cost;
    }
		
    public int compareTo(Pos o) {
        return this.cost - o.cost;
    }
}

필자는 좌표값 변수와 가중치 변수 cost를 생성해 주고 cost를 오름차순으로 재정의해줬다. 우선순위 큐에서 자동으로 최단 거리를 먼저 뽑아낼 수 있도록 하기 위해서다. 

 

 

<최종코드>

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

public class Main {
    static int dx[] = {0, 1, 0, -1};
    static int dy[] = {1, 0, -1, 0};
    static int map[][];
	
    public static class Pos implements Comparable<Pos>{
        int x, y, cost;
		
        public Pos (int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }
		
        public int compareTo(Pos o) {
            return this.cost - o.cost;
        }
    }
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
		
        int seq = 1;
        while (true) {
            int N = Integer.parseInt(br.readLine()); // 맵 크기
			
            if (N == 0) return;
			
            map = new int[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());
                }
            }
			
            System.out.println("Problem " + seq + ": "+ bfs(N));
            seq++;
        }
    }
	
    public static int bfs(int N) {
        PriorityQueue<Pos> q = new PriorityQueue<>();
        boolean[][] visited = new boolean[N][N];
        
        q.add(new Pos(0, 0, map[0][0]));
        visited[0][0] = true;
		
        while (!q.isEmpty()) {
            Pos now = q.poll();
		
            // 도착했을 경우
            if (now.x == N-1 && now.y == N-1) {
                return now.cost;
            }
			
            for (int d=0; d<4; d++) {
                int nx = now.x + dx[d];
                int ny = now.y + dy[d];
				
                if (nx < 0 || ny < 0 || nx > N-1 || ny > N-1 || visited[nx][ny]) continue;
				
                q.add(new Pos(nx, ny, now.cost + map[nx][ny]));
                visited[nx][ny] = true;
            }
        }
		
        return 0; // 의미 없음.
    }
}