백준 4485 녹색 옷 입은 애가 젤다지? (Java)

1. 문제 링크

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

 

2. 문제 및 입출력예제

 

3. 문제 풀이

그냥 풀어도 통과는 하지만 dp로 풀었을 때 메모리와 시간 측면에서 훨씬 향상된 모습을 볼 수 있다.

1번 풀이는 완전탐색이고 215676KB 792ms 라는 결과가 나왔다.

2번 풀이는 dp 이고 17848KB 180ms라는 결과가 나왔다.

 

4. 코드

1. 1번 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.io.IOException;

public class Main {
	static class Point{
		int x;
		int y;
		int num;
		public Point(int x, int y, int num) {
			super();
			this.x = x;
			this.y = y;
			this.num = num;
		}
	}
	static int N, result, map[][], clone[][];
	static int[] dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0};
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int t = 1;
		while(true) {
			result = Integer.MAX_VALUE;
			N = Integer.parseInt(br.readLine());
			if(N==0)  break;
			map = new int[N][N];
			for(int i=0;i<N;i++) {
				String[] split = br.readLine().split(" ");
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(split[j]);
				}
			}
			clone = new int[N][N];
			for(int i=0;i<N;i++) {
				Arrays.fill(clone[i], Integer.MAX_VALUE);
			}
			Queue<Point> queue = new ArrayDeque<>();
			queue.offer(new Point(0, 0, map[0][0]));
			clone[0][0] = map[0][0];
			
			while(!queue.isEmpty()) {
				Point now = queue.poll();
				if(now.x == N-1 && now.y == N-1) {
					result = Math.min(result, now.num);
				}
				for(int d=0;d<4;d++) {
					int X = now.x+dx[d];
					int Y = now.y+dy[d];
					if(X<0 || X>=N || Y<0 || Y>=N) {
						continue;
					}
					int temp = map[X][Y]+now.num;
					if(clone[X][Y] > temp) {
						clone[X][Y] = temp;
						queue.offer(new Point(X, Y, temp));
					}
					
				}
				
			}			
			sb.append("Problem "+t+": "+result).append("\n");
			t++;
		}
		System.out.println(sb);
	}	
}

2. dp 풀이

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

public class Main {

	private static final int[] dx = {1, -1, 0, 0};
	private static final int[] dy = {0, 0, -1, 1};
	private static class Point implements Comparable<Point> {
		public int x;
		public int y;
		public int minDistance;
		public Point(int x, int y, int minDistance) {
			this.x = x;
			this.y = y;
			this.minDistance = minDistance;
		}

		@Override
		public int compareTo(Point o) {
			return this.minDistance - o.minDistance;
		}
	}
	public static void main(String args[]) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = 1;
		while (true) {
			int N = Integer.parseInt(br.readLine());
			if (N == 0) {
				break;
			}

			int[][] map = new int[N][N];
			int startX = 0;
			int startY = 0;
			int endX = N - 1;
			int endY = N - 1;

			for (int i = 0; i < N; i++) {
				String[] split = br.readLine().split(" ");
				for (int j = 0; j < N; j++) {
					map[i][j] = Integer.parseInt(split[j]);
				}
			} //입력 끝

			int[][] distance = new int[N][N];
			boolean[][] visited = new boolean[N][N];
			PriorityQueue<Point> pq = new PriorityQueue<>();

			for (int i = 0; i < N; i++) {
				Arrays.fill(distance[i], Integer.MAX_VALUE);
			}
			
			distance[startX][startY] = map[startX][startY];
			pq.offer(new Point(startX, startY, distance[startX][startY]));

			while (!pq.isEmpty()) {
				Point now = pq.poll();
				if (visited[now.x][now.y]) {
					continue;
				}
				visited[now.x][now.y] = true;
				if (now.x == endX && now.y == endY) {
					break;
				}
				for (int d = 0; d < 4; d++) {
					int X = now.x + dx[d];
					int Y = now.y + dy[d];
					if ((0 <= X && X < N) && (0 <= Y && Y < N)) {
						if (distance[X][Y] > distance[now.x][now.y] + map[X][Y]) {
							distance[X][Y] = distance[now.x][now.y] + map[X][Y];
							pq.offer(new Point(X, Y, distance[X][Y]));
						}
					}
				}
			}
			sb.append("Problem ").append(T++).append(": ").append(distance[endX][endY]).append("\n");
		}
		System.out.println(sb);
	}
}