[SWEA] 1249. [S/W 문제해결 응용] 4일차 - 보급로

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD

SW Expert Academy

 

✔ 문제 조건

1. 파손된 곳 (map[r][c]!=0)은 복구 후 지나가야 한다.
   복구에 드는 비용은 map[r][c] 만큼이다.
   1-1. 파손되지 않은 곳 (map[r][c]==0)은 그냥 지나갈 수 있다.
   (문제 풀이 시에는 0만큼의 비용을 더해준다고 생각했다.)
2. 상하좌우로 이동 가능
3. 출발지 (0, 0)에서 도착지 (N-1, N-1)까지의 최소 복구 비용 구하기

 

✔ 접근 과정

1. 시작점부터 bfs를 돈다.
2. 아직 방문하지 않은 곳이라면 복구 비용을 더하며 방문한다.
3. 이미 방문한 곳이라면, 더 적은 복구 비용으로 방문할 수 있는 경우만 방문한다.
4. 도착지에 이르면 복구 비용을 반환한다.
   일반 큐를 사용한다면, 큐가 빌 때 까지 bfs를 돌며 최소 비용으로 도착지에 이를 경우를 구해야 한다.
   그러나 우선순위 큐를 사용한다면 최초로 도착지에 도달할 때의 최소 비용을 구하면 된다.

✔ 주의할 점
계속 무한루프에 빠져서 살펴보니,,
방문 확인 겸 거리 값을 갱신하는 visited 배열을 int형으로 선언할 경우 초기값이 0이다.
그런데 시작 위치의 거리값 또한 0으로 초기화한다면 0의 최소비용으로 도달하는 곳들은 모두 방문하지 않은 곳으로 생각되어 무한루프에 빠진다.
이를 해결하려면

1. v배열 초기값을 0으로 그대로 두고
   시작점 방문시 값을 1로 세팅한다.
   v[nr][nc]==0이면 방문하지 않은 곳으로 처리하며
   반환은 return min-1
2. v배열 초기값을 -1로 채우고
   시작점 방문시 값을 0로 세팅한다.
   [nr][nc]==-1이면 방문하지 않은 곳으로 처리하며
   반환은 return min

 

import java.io.*;
import java.util.*;
// 210412

public class Solution_D4_1249_보급로 {
	static int N;
	static int[][] map;
	// 시작 0,0 끝 N-1, N-1
	
	static class Pos implements Comparable<Pos>{
		int r, c, total;
		
		@Override
		public int compareTo(Pos o) {
			return Integer.compare(this.total, o.total);
		}

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

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input_D4_1249_보급로.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = stoi(br.readLine());
		
		for(int tc=1; tc<=T; tc++) {
			
			N = stoi(br.readLine());
			map = new int[N][N];
		
			for(int i=0; i<N; i++) {
				char[] c = br.readLine().toCharArray();
				for(int j=0; j<N; j++) {
					map[i][j] = c[j]-'0';
				}
			}
			
			sb.append("#" + tc +" " + bfs() + "\n");
		}
	
		System.out.println(sb.toString());
		br.close();
	}
	
	static int[] dr = {-1, 0, 1, 0};
	static int[] dc = {0, -1, 0, 1};
	
	static int bfs() {
		
		// 1. v배열 초기값을 0으로 / 시작점 방문시 값을 1로 세팅 / v[nr][nc]==0이면 방문하지 않은 곳/ return min-1
		// 2. v배열 초기값을 -1으로 / 시작점 방문시 값을 0로 세팅 / v[nr][nc]==-1이면 방문하지 않은 곳/ return min
		
		int[][] v = new int[N][N];
		for(int i=0; i<N; i++) {
			Arrays.fill(v[i], -1);
		}
		
		PriorityQueue<Pos> q = new PriorityQueue<Pos>();
		
		// 시작점
		v[0][0] = 0;
		q.offer(new Pos(0, 0, 0));
		
		Pos cur;
		int nr, nc;
		
		while(!q.isEmpty()) {			
			cur = q.poll();
			
			if(cur.r == (N-1) && cur.c == (N-1)) {
				return cur.total;
			}
			
			for(int d=0; d<4; d++) {
				nr = cur.r + dr[d];
				nc = cur.c + dc[d];
				if(nr<0 || nr>=N || nc<0 || nc>=N) continue;

				// 방문 안한 경우
				if(v[nr][nc]==-1) {
					v[nr][nc] = cur.total+map[nr][nc];
					q.offer(new Pos(nr, nc, cur.total+map[nr][nc]));
				}
				
				// 방문한 경우
				// 더 적은 total로 방문 가능한 경우만 방문
				else if(v[nr][nc]!=-1) {
					
					if(v[nr][nc] > cur.total+map[nr][nc]) {
						v[nr][nc] = cur.total+map[nr][nc];
						q.offer(new Pos(nr, nc, cur.total+map[nr][nc]));
					}
				}
			}
		}
		
		return 0;
	}
	
	static int stoi(String str) {
		return Integer.parseInt(str);
	}
}