[백준] BOJ 4485 녹색 옷 입은 애가 젤다지? (골드 4)

문제

---

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

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

---

해설

---

풀이 1. BFS

---

1. 2차원 배열에 해당 위치를 방문했을 때 비용을 누적할 수 있도록 한다.
2. 일반적으로 BFS를 통해 탐색하면, 이미 방문한 곳을 다시 방문할 수 없기 때문에,
   이미 방문한 경우에 더 적은 비용으로 해당 위치를 방문한 경우 해당 위치의 비용을 변경해주고 다시 큐에 넣어준다.

---

풀이 2. BFS + 우선순위 큐

1. 풀이 1에 우선순위 큐 적용
2. 가장 비용이 작은 것을 먼저 탐색해서 목적지에 도달하면
   이 후 도착하는 값들은 모두 해당 비용보다 크므로 모두 탐색하기 전에 종료할 수 있다.

---

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        int cnt = 1;
        while (true) {
            int N = Integer.parseInt(br.readLine());
            if(N == 0){
                break;
            }
            int[][] map = new int[N][N];
            for (int i = 0; i < N; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                }
            }
            sb.append("Problem ").append(cnt++).append(": ")
                            .append(bfs(N, map)).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    //풀이 2 (1번 풀고 다른 사람 풀이 보고 생각나서 했음 첨부터 내 머리속에서 나온거 아님 ㅠㅠ)
    private static long bfs_priority(int N, int[][] map) {
        class Point implements Comparable<Point>{
            int row;
            int col;
            int cost;

            public Point(int row, int col, int cost) {
                this.row = row;
                this.col = col;
                this.cost = cost;
            }

            @Override
            public int compareTo(Point p) {
                return cost - p.cost; //작은게 우선순위 높게
            }
        }

        int[] dy = {0, -1, 0, 1};
        int[] dx = {-1, 0, 1, 0};

        boolean[][] isVisit = new boolean[N][N];

        PriorityQueue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(0,0,map[0][0]));
        isVisit[0][0] = true;

        while (!queue.isEmpty()){
            Point point = queue.poll();
            int row = point.row;
            int col = point.col;
            int cost = point.cost;

            for (int i = 0; i < 4; i++) {
                int y = row + dy[i];
                int x = col + dx[i];

                if(y == N - 1 && x == N - 1){
                    return cost + map[y][x];
                }

                if ((y < 0 || y >= N || x < 0 || x >= N) || isVisit[y][x]) {
                    continue;
                }

                isVisit[y][x] = true;
                queue.offer(new Point(y, x, map[y][x] + cost));
            }
        }
        return 0;
    }

    //풀이 1
    private static long bfs(int N, int[][] map) {
        class Point{
            int row;
            int col;
            int cost;

            public Point(int row, int col, int cost) {
                this.row = row;
                this.col = col;
                this.cost = cost;
            }
        }

        int[] dy = {0, -1, 0, 1};
        int[] dx = {-1, 0, 1, 0};

        boolean[][] isVisit = new boolean[N][N];
        int[][] costs = new int[N][N];

        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(0,0,map[0][0]));
        isVisit[0][0] = true;
        costs[0][0] = map[0][0];

        while (!queue.isEmpty()){
            Point point = queue.poll();
            int row = point.row;
            int col = point.col;
            int cost = point.cost;

            for (int i = 0; i < 4; i++) {
                int y = row + dy[i];
                int x = col + dx[i];

                if(y < 0 || y >= N || x < 0 || x >= N){
                    continue;
                }

                //아직 방문하지 않았다면 해당 좌표 + 이전 비용 + 현재 비용
                if(!isVisit[y][x]){
                    queue.add(new Point(y, x, cost + map[y][x]));
                    costs[y][x] = cost + map[y][x];
                    isVisit[y][x] = true;
                }
                //이미 방문했지만 비용감소가 가능한 경우
                if(isVisit[y][x] && costs[y][x] > (cost + map[y][x])){
                    queue.add(new Point(y, x, cost + map[y][x]));
                    costs[y][x] = cost + map[y][x];
                }
            }
        }
        return costs[N-1][N-1];
    }
}

---

결론

---

 

이때는 Priority Queue를 사용하는 것이 익숙하지 않았는데 지나고 나서 보니 많이 성장한 것 같아서 뿌듯하다!

---