[Java] SW Expert Academy 1249번 문제: [S/W 문제해결 응용] 4일차 - 보급로 (BFS, 너비우선탐색)

--- 문제 ---

• [S/W 문제해결 응용] 4일차 - 보급로

2차 세계 대전에서 연합군과 독일군의 전투가 점점 치열해지고 있다.
전투가 진행중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.
그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.
전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.
공병대는 출발지(S) 에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.
도로가 파여진 깊이에 비례해서 복구 시간은 증가한다.
출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.
깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

 

--- 코드 ---

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Sw1249 {
	
	// 지도에서 움직일 방향 (동,서,남,북)
	public static final int[][] DIRECTION = {{0,1},{0,-1},{1,0},{-1,0}};
	public static int[][] map ;
	public static int[][] visited;
	
	public static void main(String[] args) throws FileNotFoundException {

		System.setIn(new FileInputStream("./src/1249.txt"));

		Scanner sc = new Scanner(System.in);
		
		int T=sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++) {
			
			int n = sc.nextInt();
			map = new int[n][n];
			visited = new int[n][n];
			
			// 1. input
			for(int r=0; r<n; ++r) {
				String[] num2 = sc.next().split("");
				
				for(int i=0; i<n; ++i) {
					map[r][i] =  Integer.parseInt(num2[i]);
					visited[r][i] = -1;
				}
			}
			
			
			// 2. start bfs
			Queue<LinkedList<Integer>> check = new LinkedList<LinkedList<Integer>>();
			LinkedList<Integer> tmp = new LinkedList<Integer>();
			tmp.add(0); tmp.add(0);
			check.add(tmp);
			visited[0][0] = 0;
			
			while(!check.isEmpty()) {
				LinkedList<Integer> current = check.poll();
				int startx = current.get(0);
				int starty = current.get(1);
				
				for( int[] direction : DIRECTION ) {
					int nextx = startx + direction[0];
					int nexty = starty + direction[1];
					
					// 2-1. 해당 방향으로 움직인 좌표가 지도 범위 안에 있으면
					if(nextx>=0 && nextx<n && nexty>=0 && nexty<n) {
						// 현재 이동 값 계산
						int step = visited[starty][startx]+map[nexty][nextx];
						// 2-1-1. 움직인 좌표를 방문해본 적이 없거나 
						// 계산된 이동 값이 기존 값보다 작은 경우
						if(visited[nexty][nextx]==-1 || visited[nexty][nextx]> step) {
							// queue에 해당 좌표 추가 하고 이동 값 갱신
							tmp = new LinkedList<Integer>();
							tmp.add(nextx);
							tmp.add(nexty);
							check.add(tmp);
							visited[nexty][nextx] = step;
						}
					}
				}
			}
			
			
			// 3. print result
			System.out.printf("#%d %d%n",test_case,visited[n-1][n-1]);
			
		}
			
	}

}

 

--- 출처 ---

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1

SW Expert Academy