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

접근 방법

1. BFS로 접근하였습니다. 경로에 대해 저장할 이차원 배열 int[][] sum을 선언하여 이미 방문한 경로인 경우에는 현재 방문할 예정인 경로와 이미 방문한 경로의 값을 비교해 현재 방문할 예정인 경로가 더 작은 경우 큐에 다시 넣어주었습니다.

2. 특히, 이 문제의 경우 그냥 큐를 사용하였더니 시간초과가 났습니다. 따라서, 우선순위 큐를 통해 작은 값들을 먼저 돌게 하여 시간 초과 문제를 해결할 수 있었습니다.

 

구현 설명

1.  class Point에는 x,y 좌표와 현재 경로에 대한 합을 저장하기 위한 value를 선언하였습니다.

2.  int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}} 의 경우 기존에 상하좌우로 진행하였던 방향과는 다르게 좌우상하로 진행하였습니다. 

public class Solution_1249 {
	private static int result;
	private static int N;
	private static boolean[][] visited;
	private static int[][] maps;
	
	static class Point implements Comparable<Point>{
		int x,y;
		int value;		

		public Point(int x, int y, int value) {
			super();
			this.x = x;
			this.y = y;
			this.value = value;
		}

		@Override
		public int compareTo(Point o) {
			return this.value - o.value;
		}

	}
	
	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());
			
			maps = new int[N][N];	
			visited = new boolean[N][N];
			
			for (int i = 0; i < N; i++) {
				String tmp = br.readLine();
				for (int j = 0; j < N; j++) {
					maps[i][j] = tmp.charAt(j) - '0';
				}
			}
			
			result = Integer.MAX_VALUE;
			
			solve();
			
			sb.append(String.format("#%d %d\n", test_case, result));
		}
		System.out.println(sb.toString());
	}
	
	private static int[][] dir = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};//좌우상하
	
	private static void solve() {
		PriorityQueue<Point> queue = new PriorityQueue<Point>();
		queue.add(new Point(0, 0, maps[0][0]));
		
		int[][] sum = new int[N][N];//경로 합
		sum[0][0] = maps[0][0];
		
		while(!queue.isEmpty()) {
			Point now = queue.poll();
			int nowX = now.x;
			int nowY = now.y;
			int nowValue = now.value;
			
			visited[nowX][nowY] = true;
			
			if(nowX == N-1 && nowY == N-1) {
				result = Math.min(result, nowValue);
				continue;
			}
			
			for (int i = 0; i < dir.length; i++) {
				int nextX = nowX + dir[i][0];
				int nextY = nowY + dir[i][1];
				
				if(nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
				if(visited[nextX][nextY]) {
					//이미 방문한 경우 현재 진행할 경로와 이미 방문했던 경로를 비교해 현재 진행할 경로가 더 작은 경우 큐에 삽입
					if(nowValue + maps[nextX][nextY] < sum[nextX][nextY]) {
						sum[nextX][nextY] = nowValue + maps[nextX][nextY];
						queue.add(new Point(nextX, nextY, sum[nextX][nextY]));						
					}			
				}else {					
					sum[nextX][nextY] = nowValue + maps[nextX][nextY];
					queue.add(new Point(nextX, nextY, sum[nextX][nextY]));
				}
			}
		}
		
	}
	
}