녹색 옷 입은 애가 젤다지?(BJ_G4_4485)

1. 문제 링크

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

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

---

 

2. 나의 코드

메모리: 21020KB 
시간: 264ms 
코드 길이: 2376B
시간 복잡도 : O(N^2logN)
설명
- 다익스트라 알고리즘 사용
- 방문체크, map, result 이렇게 3가지의 2차원 배열을 사용
- bfs를 활용해서 4방 탐색을 하면서 우선순위큐에 넣는다.
- 우선순위큐에서 하나씩 빼면서 전까지의 경로와 자신의 값을 더한 값을 result와 비교하여 작다면 값을 변경한다.

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

public class BJ_4485 {
    static class Node implements Comparable<Node> {
        int r, c, weight;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.weight, o.weight);
        }
    }

    static int N;
    static int[][] map, result;
    static boolean[][] visited;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int idx = 1;
        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0) break;
            map = new int[N][N];
            result = 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());
                    result[i][j] = Integer.MAX_VALUE;
                }
            }

            dijkstra();
            System.out.printf("Problem %d: %d\n", idx++, result[N - 1][N - 1]);
        }
    }

    private static void dijkstra() {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        result[0][0] = map[0][0];
        visited[0][0] = true;
        pq.offer(new Node(0, 0, map[0][0]));

        while (!pq.isEmpty()) {
            Node now = pq.poll();

            for (int d = 0; d < 4; d++) {
                int nr = now.r + dr[d];
                int nc = now.c + dc[d];

                if (isValid(nr, nc) && !visited[nr][nc] && now.weight + map[nr][nc] < result[nr][nc]) {
                    visited[nr][nc] = true;
                    result[nr][nc] = now.weight + map[nr][nc];
                    pq.offer(new Node(nr, nc, result[nr][nc]));
                }
            }
        }
    }

    private static boolean isValid(int r, int c) {
        return 0 <= r && r < N && 0 <= c && c < N;
    }
}

 

---

 

3. 정답 코드

package study0216.src;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Baekjoon4485 {
    static int map[][];
    static boolean visited[][];
    static int minValue[][];
    final static int INF = Integer.MAX_VALUE;
    static int dr[] = {0, 0, 1, -1};
    static int dc[] = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int count = 0;
        while (true) {
            ++count;
            int N = Integer.parseInt(bf.readLine().trim());
            if (N == 0) System.exit(0);

            visited = new boolean[N][N];
            map = new int[N][N];
            minValue = new int[N][N];
            for (int i = 0; i < N; i++) {
                st = new StringTokenizer(bf.readLine());
                for (int j = 0; j < N; j++) {
                    map[i][j] = Integer.parseInt(st.nextToken());
                    minValue[i][j] = INF;
                }
            }

            int r = 0, c = 0;
            visited[0][0] = true;
            minValue[0][0] = map[0][0];

            for (int visit = 0; visit < N * N; visit++) {
                // 인접 부분의 거리를 정리해야 함

                for (int d = 0; d < 4; d++) {
                    int nr = r + dr[d];
                    int nc = c + dc[d];
                    if (nr < 0 || nc < 0 || nr >= N || nc >= N || visited[nr][nc]) continue;

                    minValue[nr][nc] = Math.min(minValue[nr][nc], map[nr][nc] + minValue[r][c]);

                }

                //정리가 완료된 후 최소 거리인 미방문 위치로 가야 함
                int nextr = -1;
                int nextc = -1;
                int minLocation = INF;

                for (int i = 0; i < N; i++) {
                    for (int j = 0; j < N; j++) {
                        if (visited[i][j]) continue;
                        if (nextr == -1 || minLocation > minValue[i][j]) {
                            nextr = i;
                            nextc = j;
                            minLocation = minValue[i][j];
                        }
                    }
                }
                if (nextr == -1) break;
                r = nextr;
                c = nextc;
                visited[r][c] = true;
            }
            System.out.println("Problem " + count + ": " + minValue[N - 1][N - 1]);

        }
    }
}

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

public class Main {
    static int N;
    static int[][] map, memo;
    static boolean[][] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int tc = 1;
        while (true) {
            N = Integer.parseInt(br.readLine());
            if (N == 0)
                break;
            map = new int[N][];
            memo = new int[N][N];
            Arrays.stream(memo).forEach(r -> Arrays.fill(r, Integer.MAX_VALUE));
            visited = new boolean[N][N];
            for (int n = 0; n < N; n++)
                map[n] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            start();
            sb.append("Problem ").append(tc++).append(": ").append(memo[N-1][N-1]).append("\n");
        }
        System.out.println(sb);
    }

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

    private static void start() {
        PriorityQueue<Pos> pq = new PriorityQueue<>();
        pq.offer(new Pos(0, 0, map[0][0]));

        while (!pq.isEmpty()) {
            Pos p = pq.poll();
            if (p.r == N - 1 && p.c == N - 1)
                break;
            visited[p.r][p.c] = true;
            for (int d = 0; d < 4; d++) {
                int nr = p.r + dr[d];
                int nc = p.c + dc[d];
                if (!isIn(nr, nc) || visited[nr][nc])
                    continue;
                if (p.w + map[nr][nc] < memo[nr][nc]) {
                    memo[nr][nc] = p.w + map[nr][nc];
                    pq.offer(new Pos(nr, nc, memo[nr][nc]));
                }
            }
        }
    }

    private static boolean isIn(int r, int c) {
        return r >= 0 && r < N && c >= 0 && c < N;
    }

    static class Pos implements Comparable<Pos> {
        int r, c, w;

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

        @Override
        public int compareTo(Pos o) {
            return Integer.compare(this.w, o.w);
        }
    }
}

 

---

 

4. 배운 점

- 2차원 배열을 초기화 하는 방법도 Arrays.fill(minDistance[i], Integer.MAX_VALUE); 사용이 가능하다.

 

- 다익스트라 공부를 자주하자.