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]; } }