[SWEA] 1249 - 보급로

[문제링크]

SW Expert Academy

 

0. 모든 경우의 수를 탐색 - BFS

  - 같은 공간 큰 cost를 가지고 접근할 경우 더이상 진행하지 않으므로, DFS보다 수행횟수가 적다

  - 외각을 -1로 감싸 나가지 못하도록 처리

 

1. (1, 1) 좌표부터 bfs 진행 후 N,N좌표의 cost가 최소 cost

 

개선점

1. 현재 bfs는 2-3-4순으로 진입시 3,4에 대해선 진행하지 않지만, 4-3-2순으로 진입시 4,3,2 전부 실행하게된다.

  - priority queue를 이용해 해결 가능

 

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

public class Solution{
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};
	
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			int N = pint(br.readLine());
			int[][] map = new int[N+2][N+2];
			int[][] cost = new int[N+2][N+2];
			
			//외곽설정, cost초기화
			for (int i = 0; i < N+2; i++) {
				map[0][i]=-1;map[N+1][i]=-1;
				map[i][0]=-1;map[i][N+1]=-1;
				Arrays.fill(cost[i], Integer.MAX_VALUE);
			}
			
			//입력받기
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i+1][j+1]=s.charAt(j)-'0';
				}
			}
			
			Queue<int[]> qu = new LinkedList<>();
			qu.offer(new int[] {1,1});
			cost[1][1]=0;
			
			while(!qu.isEmpty()) {
				int[]cur = qu.poll();
				int curCost = cost[cur[0]][cur[1]];
				
				//더 작은 코스트로 진행할 수 있다면
				for (int i = 0; i < 4; i++) {
					int tx=cur[0]+dx[i], ty=cur[1]+dy[i];
					
					if(map[ tx ][ ty ]!=-1 && curCost + map[ tx ][ ty ] < cost[ tx ][ ty ]) {
						qu.offer(new int[] {tx, ty});
						cost[ tx ][ ty ]=curCost+map[ tx ][ ty ];
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(cost[N][N]).append("\n");
		}
		System.out.println(sb);
	}
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면