[파이썬, 자바] 백준 4485 : 녹색 옷 입은 애가 젤다지? (골드4)

[파이썬, 자바] 백준 4485 : 녹색 옷 입은 애가 젤다지? (골드4)

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

---

풀이

방향성 생각

• 다익기본
• 배열로 이동할 때, 간선 대신 배열에 저장된 값을 간선 가중치라고 생각해서 풀이한다.

 

---

파이썬

import sys
import heapq as hq

input = lambda : sys.stdin.readline().strip()
inside = lambda x,y: 0<=x<N and 0<=y<N
dires = [(1,0),(0,1),(-1,0),(0,-1)]
INF = float('inf')

count = 1
while True:

    N = int(input())

    if not N:
        break

    arr = [list(map(int,input().split())) for _ in range(N)]

    V = [[INF]*N for _ in range(N)]
    V[0][0] = 0

    heap = [(0,0,0)]
    while heap:
        t,x,y = hq.heappop(heap)

        for dx,dy in dires:
            nx,ny = x+dx,y+dy

            if inside(nx,ny) and t+arr[ny][nx] < V[ny][nx]:
                V[ny][nx] = t+arr[ny][nx]
                hq.heappush(heap,(t+arr[ny][nx],nx,ny))

    print(f"Problem {count}: {V[-1][-1]+arr[0][0]}")
    count += 1

자바

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

public class Main {
    static int N;
    static int[][] arr;
    static int[][] dires = {{1,0},{0,1},{-1,0},{0,-1}};
    static int INF = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {

        int TC = 1;
        BufferedReader br = new BufferedReader( new InputStreamReader(System.in));
        while (true) {

            int N = Integer.parseInt(br.readLine());

            if (N==0) {
                break;
            }

            int[][] arr = 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] = Integer.parseInt(st.nextToken());
                }
            }

            PriorityQueue<int[]> heap = new PriorityQueue<>((cur,next) -> Integer.compare(cur[0],next[0]));
            heap.offer(new int[] {0,0,0});

            int[][] V = new int[N][N];
            for (int j=0; j<N; j++) {
                Arrays.fill(V[j],INF);
            }
            V[0][0] = 0;

            while (!heap.isEmpty()) {

                int[] cur = heap.poll();
                int t=cur[0], x=cur[1], y=cur[2];

                for (int[] dire: dires) {
                    int nx = x+dire[0], ny=y+dire[1];
                    if (0<=nx && nx<N && 0<=ny && ny<N && t+arr[ny][nx]<V[ny][nx]) {
                        heap.offer(new int[] {t+arr[ny][nx],nx,ny});
                        V[ny][nx] = t + arr[ny][nx];
                    }
                }
            }
            System.out.printf("Problem %d: %d", TC, V[N-1][N-1]+arr[0][0]);
            System.out.println();
            TC += 1;
        }

    }
}

---

코멘트

• .