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

문제

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&problemLevel=4&contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=4&pageSize=10&pageIndex=1# 

SW Expert Academy

풀이

복구 시간이 가장 짧은 경로를 찾으라고 하였으므로 BFS를 이용한다.

이차원 배열을 이용하여 각 좌표에 도달하는 데 걸리는 시간을 넣어준다.

중요한것은 bfs 내에서의 조건문이다. 방문하지 않았거나 더 적은 시간이 걸렸을 경우에만 update 해준다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int board[][];
	static int n;
	
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
				
		int T = Integer.parseInt(br.readLine());
		for(int test_case = 1; test_case <= T; test_case++)
		{
			n = Integer.parseInt(br.readLine());
			
			board = new int [n][n];
			
			for(int i=0;i<n;i++) {
				String str = br.readLine();
				for(int j=0;j<n;j++) {
					board[i][j] = str.charAt(j) - '0';
				}
			}
			
			int result = bfs();
			System.out.println("#"+test_case+" "+result);

		}
		
	}
	
	
	static int bfs() {
		Queue<int []> que = new LinkedList<>();
		int visited[][] = new int [n][n];
		
		for(int i=0;i<n;i++) {
			Arrays.fill(visited[i], -1);
		}
		
		int dx [] = {-1, 0, 1, 0};
		int dy [] = {0, -1, 0, 1};
		
		int result = n*n;
		
		que.add(new int [] {0,0});
		visited[0][0] = board[0][0];
		
		while(!que.isEmpty()) {
			int cur [] = que.poll();
			
			if(cur[0] == n-1 && cur[1] == n-1) {
				result = Math.min(visited[n-1][n-1], result) ;
			}
				
			for(int i=0;i<4;i++) {
				int nx = cur[0] + dx[i];
				int ny = cur[1] + dy[i];
				
				if(nx >= n || ny >= n || nx < 0 || ny < 0) continue;
				
				if(visited[nx][ny] == -1 || visited[nx][ny] > board[nx][ny] + visited[cur[0]][cur[1]]) {
					visited[nx][ny] = board[nx][ny] + visited[cur[0]][cur[1]];
					que.add(new int[] {nx, ny});
				}
				
			}
		
		}
		
		return result;
	}
}