[SWEA] 1249 보급로

SW Expert Academy 1249 보급로

알고리즘 풀이는 오랜만에 올리는 것 같다.
앞으로는 매일매일 꾸준히 올려봐야겠다.

BFS로 접근해서 풀었는데, 이 문제의 핵심은 아래 한줄이다.

if(!visited[tempx][tempy]|| cmap[tempx][tempy]> map[tempx][tempy]+cmap[posx][posy])

기존 BFS에서는 visited 배열을 이용해서 방문한 곳을 다시 방문하지 않는다.
하지만 이 문제의 경우 다른 경로를 통해 i,j 위치에 더 적은 비용으로 방문하는 경우가 있다.
바로 이 경우를 위해서 이미 방문하였더라도 or 연산자 ‘||’를 이용해서 기존 cost보다 더 적은 비용으로 방문할 수 있다면 해당 위치의 값을 바꾸어 주어야한다.

이 조건을 생각하기까지 시간이 좀 오래걸렸다.

package _04._0412;

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

public class SWEA1249Supply {
	private static boolean[][] visited;
	private static int[] dx = {1,0,-1,0};		
	private static int[] dy = {0,1,0,-1};		
	private static int startx, starty,destx, desty, N;
	private static int[][] cmap, map;

	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));
		int TC = Integer.parseInt(br.readLine());
		for (int testCase = 1; testCase <= TC; testCase++) {
//			if(testCase<=4)continue;
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			visited = new boolean[N][N];
			for (int i = 0; i < N; i++) {
				String line =br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = line.charAt(j)-'0';
				}
			}
			cmap = new int[N][N];
			for (int i = 0; i < N; i++) {
				Arrays.fill(cmap[i], Integer.MAX_VALUE);
			}
			startx =  starty = 0;
			destx =  desty = N-1;
			System.out.println("#"+testCase+" "+bfs());
		}
	}

	private static int bfs() {
		Queue<int[]> Q = new LinkedList<>();
		Q.offer(new int[] {startx,starty});
		cmap[startx][starty] =0;
		visited[startx][starty] = true;
		while (!Q.isEmpty()) {
			int[] temp = Q.poll();
			int posx = temp[0];
			int posy = temp[1];
			for (int i = 0; i < 4; i++) {
				int tempx = posx +dx[i];
				int tempy = posy +dy[i];
				if(tempx <0 || tempy<0 || tempx>=N || tempy >=N) continue; //값이 범위를 벗어나는 경우 
				if(!visited[tempx][tempy]|| cmap[tempx][tempy]> map[tempx][tempy]+cmap[posx][posy]) { //방문했거나 || 값이 작은경우 
					visited[tempx][tempy] = true;
					cmap[tempx][tempy] = map[tempx][tempy]+cmap[posx][posy];
					Q.offer(new int[] {tempx,tempy});
				}
			}
		}
		return cmap[destx][desty];
	}
}