SWEA - 보급로 1249번 (JAVA)

❓ 문제 - SWEA 보급로 1249번 - JAVA 풀이법

 

출처 

(https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD)

 

 

📝 문제해결법

1. 이 문제는 DP + BFS로 풀이했다.

• BFS 내에서 visited라는 2차원 배열을 만들어서 방문체크와 동시에 DP로 활용했다.
• 인접한 네 곳을 방문할 때는 기존 지나갔던 비용보다 현재 비용이 더 적을 경우에만 그곳을 방문할 수 있게 구현하였다.
• 그리고 큐에서 꺼낸 노드가 도착치 노드인 경우 출발지부터 도착지까지 걸리는 비용들을 최솟값으로 계속 갱신한 후 답으로 출력할 수 있게 구현했다.

2. 느낀점

• 처음에 조금 더 효율적으로 풀어보고자 플로이드워셜인가..? 하면서 접근했지만 아무리봐도 BFS였고.. DP를 활용해서 풀었다.

 

💻 소스코드

// SWEA - 보급로(1249번)
// BFS

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


public class Solution_1249 {
	public static int n;
	public static int[][] map;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};

	public static class Node {
		int x;
		int y;
		int dis;
		public Node(int x, int y, int dis) {
			this.x = x;
			this.y = y;
			this.dis = dis;
		}
	}

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

		int TC = Integer.parseInt(br.readLine());
		for(int test_case=1;test_case<=TC;test_case++){
			n = Integer.parseInt(br.readLine());
			map = new int[n][n];

			for(int i=0;i<n;i++) {
				String[] data = br.readLine().split("");
				for(int j=0;j<n;j++) {
					map[i][j] = Integer.parseInt(data[j]);
				}
			}
			int ans = bfs();
			sb.append("#"+test_case).append(" ").append(ans).append("\n");
		}

		System.out.println(sb.toString());

	}

	public static int bfs() {
		int[][] visited = new int[n][n];
		for(int i=0;i<n;i++) {
			Arrays.fill(visited[i], Integer.MAX_VALUE);
		}
		Queue<Node> q = new LinkedList<Node>();
		visited[0][0] = 0;
		q.offer(new Node(0, 0, 0));
		int dis = Integer.MAX_VALUE;
		while(!q.isEmpty()) {
			Node node = q.poll();
			if(node.x == n-1 && node.y == n-1) {
				dis = Math.min(dis, node.dis);
				continue;
			}

			for(int d=0;d<4;d++) {
				int nx = node.x + dx[d];
				int ny = node.y + dy[d];
				if(0 <= nx && nx < n && 0 <= ny && ny < n) {
					int distance = node.dis + map[nx][ny];
                    // 만약 이미 지나갔던 최단비용보다 더 작은 비용으로 지나갈 수 있다면
                    // 값을 갱신해주고 Queue에 넣어주는 부분
					if(visited[nx][ny] > distance) {
						visited[nx][ny] = distance;
						q.add(new Node(nx, ny, distance));
					} 
				}
			}
		}

		return dis;

	}

}