[SWEA / Java] 1249번: 보급로 (D4)

문제 풀이 날짜: 2023.05.19
포스트 작성일: 2023.05.19

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

Software Expert Academy 1249번 : 보급로 (D4) (문제 링크)

 

키워드

동적 계획법(DP), BFS

 

풀이 접근법

• 일반적인 BFS와는 다르게 갔던 장소(visited[r][c] = true)를 다시 갈 수 있어야 한다. 또, 새롭게 발견한 경로의 최소 비용으로 갱신하는 부분이 필요하다.
• 따라서 최소비용은 DP 배열에 갱신하고, DP값이 갱신된 노드는 다시 Queue에 추가하여 탐색을 계속한다.
• 즉, 어떤 점 (r, c)는 왼쪽(r, c - 1)과 위쪽(r - 1, c)에서 방문할 수 있다. 여기서 이미 왼쪽 점으로부터 방문하여 queue에 현재의 점(r, c)이 추가되었다고 해보자.
  • 그런데 이 점은 위쪽에서부터 방문한 값이 최소인 상황이다. 이런 상황에서 위쪽으로부터 온 DP값으로 비용이 갱신되었다면 다시 BFS 탐색을 해주어야 이 점 (r, c)와 이어진 다른 점들까지 연쇄적으로 최솟값을 갱신할 수가 있다.
  • 그렇지 않으면 해당 점까지의 최솟값은 갱신될 수 있어도, 이후로 이어진 경로들까지 이 최신 정보가 반영되지 않는다.
  • 결국 방문할 점을 Queue에 추가하는 조건이 1.visited 여부 2.새 값 갱신 여부 이렇게 총 2가지인 것.

 

코드

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

public class SWEA1249 {
	
	private static int N;
	private static int[] dx = {1, 0, -1, 0};
	private static int[] dy = {0, 1, 0, -1};
	
	private static int[][] matrix;
	private static int[][] DP;
	private static boolean[][] visited;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int T = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		for(int test_case = 1; test_case <= T; test_case++) {
			N = Integer.parseInt(br.readLine());
			
			matrix = new int[N][N];
			DP = new int[N][N];
			visited = new boolean[N][N];
			
			for(int i = 0; i < N; i++) {
				char[] lines = br.readLine().toCharArray();
				for(int j = 0; j < N; j++) {
					matrix[i][j] = lines[j] - '0';
					DP[i][j] = Integer.MAX_VALUE;
				}
			}
			
			BFS(0, 0);
			
			sb.append("#" + test_case + " ").append(DP[N - 1][N - 1]).append('\n');
		}

		System.out.print(sb);
	}
	
	public static void BFS(int startR, int startC) {
		Queue<Node> queue = new LinkedList<>();
		queue.add(new Node(startR, startC));
		DP[startR][startC] = 0;
		visited[startR][startC] = true;
		
		while(!queue.isEmpty()) {
			Node n = queue.poll();
			
			int nr = 0;
			int nc = 0;
			for(int i = 0; i < dx.length; i++) {
				nr = n.row + dy[i];
				nc = n.col + dx[i];
				
				if(isValid(nr, nc)) {
					//이미 방문한 적 있더라도 더 작은 DP값이 발견되면 다시 방문
					if(!visited[nr][nc] || DP[n.row][n.col] + matrix[nr][nc] < DP[nr][nc]) {
						DP[nr][nc] = DP[n.row][n.col] + matrix[nr][nc];
						visited[nr][nc] = true;
						queue.add(new Node(nr, nc));	
					}
				}
			}
		}
		
		return;
	}
	
	public static boolean isValid(int row, int col) {
		return (row >= 0 && col >= 0 && row < N && col < N);
	}

}

class Node{
	int row;
	int col;
	
	public Node(int row, int col) {
		this.row = row;
		this.col = col;
	}
}

---

BFS와 DP가 결합된 형태는 처음 풀어보았다. 문제의 댓글을 보니 다익스트라로 접근할 수도 있다고 한다. 여기서는 DP가 갱신되는 시점을 정하는 것과 방문한 점을 또 다시 방문할 수 있도록 조건을 적절히 수정해주는 것이 매우 중요했다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week8/day5/SWEA1249.java