SWEA - 1249번 보급로

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=1249&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

 

 

 

 

요즘 DP를 풀고 있어서 그런지 이 문제도 보고서 DP로 풀면 좋겠다는 생각을 했다. 그래서 DP로 풀었는데 모든 테스트케이스를 통과하지 못했다.. 이유를 알고 보니 문제에서 '상하좌우'로 움직인다고 했다. 만약 '우하'로만 움직였다면 DP로 푸는 풀이가 통했을 것이다.

 

 

 

 

시도 - DP

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class swea_보급로dp {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수
		
		for(int t = 1; t <= T; t++) {
			int N = Integer.parseInt(br.readLine());
			int[][] graph = new int[N][N];
			
			for(int i = 0; i < N; i++) {
				String input = br.readLine();
				
				for(int j = 0; j < N; j++) {
					graph[i][j] = input.charAt(j) - '0';				
				}
			}
			
			//구현
			int[][] dp = new int[N][N];
			
			for(int i = 1; i < N; i++) {
				dp[i][0] = dp[i - 1][0] + graph[i][0];
			}
			
			for(int i = 1; i < N; i++) {
				dp[0][i] = dp[0][i - 1] + graph[0][i];
			}
			
			for(int i = 1; i < N; i++) {
				for(int j = 1; j < N; j++) {
					dp[i][j] = graph[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
				}
			}
			
			//출력
			int answer = dp[N - 1][N - 1];
			
			System.out.println("#" +  t + " " + answer);
		}
	}

}

 

 

 

 

 

 

정답 코드 - 다익스트라

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

public class Solution {
	static int N;
	static int[][] graph;
	static boolean[][] visited;
	static int[][] dist;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	
	static class Dot implements Comparable<Dot> {
		int x, y, time;

		public Dot(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}

		@Override
		public int compareTo(Dot o) {
			return this.time - o.time;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(br.readLine()); //테스트 케이스의 개수
		
		for(int t = 1; t <= T; t++) {
			N = Integer.parseInt(br.readLine());
			graph = new int[N][N];
			
			for(int i = 0; i < N; i++) {
				String input = br.readLine();
				
				for(int j = 0; j < N; j++) {
					graph[i][j] = input.charAt(j) - '0';				
				}
			}
			
			//구현
			visited = new boolean[N][N];
			
			dist = new int[N][N];
			for(int d[] : dist) { //거리 무한으로 초기화
				Arrays.fill(d, Integer.MAX_VALUE);
			}
			
			dijkstra(); //다익스트라
			
			//출력
			System.out.println("#" +  t + " " + dist[N-1][N-1]);
		}
	}

	public static void dijkstra() {
		PriorityQueue<Dot> queue = new PriorityQueue<>();
		
		queue.add(new Dot(0, 0, graph[0][0])); //시작 좌표
		dist[0][0] = graph[0][0];
		
		while(!queue.isEmpty()) {
			Dot dot = queue.poll();
			
			if(dot.x == N - 1 && dot.y == N - 1) { //종료 조건
				return;
			}
			
			if(visited[dot.x][dot.y]) continue;
			
			visited[dot.x][dot.y] = true;
			
			for(int i = 0; i < 4; i++) {
				int nx = dot.x + dx[i];
				int ny = dot.y + dy[i];
				
				if(0 <= nx && nx < N && 0 <= ny && ny < N) {
					if(dist[dot.x][dot.y] + graph[nx][ny] < dist[nx][ny]) { //더 최소인 곳이 있으면
						dist[nx][ny] = dist[dot.x][dot.y] + graph[nx][ny];
						queue.add(new Dot(nx, ny, dist[nx][ny]));
					}
				}
			}
		}
	}
	
}

 

 

 

 

 

정답

 

 

 

 

 

백준의 '녹색 옷 입은 애가 젤다지?'와 같이 다익스트라를 써서 (0,0)에서 (n-1, n-1)까지 최소 비용으로 가는 똑같은 풀이의 문제였다.

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

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