[SWEA] #1249 - 보급로

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

전투가 진행 중인 지역은 대규모 폭격과 시가전 등으로 인해 도로 곳곳이 파손된 상태이다.

그림 1(a)에서와 같이 도로들은 전투로 인해 트럭이나 탱크와 같은 차량들이 지날 갈 수 없다.

전투에서 승리하기 위해서는 기갑사단과 보급부대가 신속하게 이동하기 위한 도로가 있어야 한다.

공병대는 출발지(S)에서 도착지(G)까지 가기 위한 도로 복구 작업을 빠른 시간 내에 수행하려고 한다.

도로가 파인 깊이에 비례해서 복구 시간은 증가한다.

출발지에서 도착지까지 가는 경로 중에 복구 시간이 가장 짧은 경로에 대한 총 복구 시간을 구하시오.

깊이가 1이라면 복구에 드는 시간이 1이라고 가정한다.

그림 1 (a) 파손된 도로                                                                                                                             (b) 지도 형태와 이동 방향

지도 정보는 그림 1(b)과 같이 2차원 배열 형태로 표시된다.

출발지는 좌상단의 칸(S)이고 도착지는 우하단의 칸(G)이 된다.

이동 경로는 상하좌우 방향으로 진행할 수 있으며, 한 칸씩 움직일 수 있다.

지도 정보에는 각 칸마다 파인 도로의 깊이가 주어진다. 현재 위치한 칸의 도로를 복구해야만 다른 곳으로 이동할 수 있다.
 

그림 2 지도 정보

이동하는 시간에 비해 복구하는데 필요한 시간은 매우 크다고 가정한다.

따라서, 출발지에서 도착지까지 거리에 대해서는 고려할 필요가 없다.

지도 정보는 그림 2에서 보듯이 2차원 배열의 형태이다.

출발지(S)와 도착지(G)는 좌상 단과 우하단이 되고 입력 데이터에서는 0으로 표시된다.

출발지와 도착지를 제외한 곳이 0인 것은 복구 작업이 불필요한 곳이다.

다음과 같은 지도에서 복구 작업 시간이 최소인 시간은 2이고 회색으로 칠해진 경로가 된다.
 

 

💡 아이디어

---

이 문제는 다양한 방법으로 해결할 수 있는데 나는 BFS로 문제를 해결했다.

(DFS로 풀 경우 시간이 많이 걸린다는 이야기가 있었다.)

일반적인 BFS와 달리 현재 지점에서 이동했을 때 소요시간이 가장 적게 걸리는 루트를 비교하면서

탐색을 이어나가야 한다.

 

💡 소스코드

---

package SWEA;

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

class Pos {
	int x;
	int y;

	Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class SWEA_P1249_보급로 {
	static int N, MIN;
	static int[][] map, weight;
	static boolean[][] visited;
	// 상하좌우에 해당하는 방향
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1249_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());

			init();// 초기화

			// 입력
			for (int i = 0; i < N; i++) {
				String s = br.readLine();
				for (int j = 0; j < N; j++) {
					map[i][j] = s.charAt(j) - '0';
				}
			}

			BFS();
			System.out.println("#" + TC + " " + MIN);
		}
		br.close();
	}

	public static void BFS() {
		Queue<Pos> queue = new LinkedList<Pos>();

		// queue에 (0,0) 추가
		queue.add(new Pos(0, 0));
		visited[0][0] = true;

		while (!queue.isEmpty()) {
			Pos P = queue.poll();

			if (P.x == N - 1 && P.y == N - 1) {
				if (MIN > weight[P.x][P.y])
					MIN = weight[P.x][P.y];
				continue;
			}

			if (MIN <= weight[P.x][P.y])
				continue;

			for (int i = 0; i < 4; ++i) {
				int nx = P.x + dx[i];
				int ny = P.y + dy[i];

				// 이동하려는 방향이 map범위 안이라면
				if (nx < 0 || ny < 0 || nx >= N || ny >= N)
					continue;

				if (!visited[nx][ny] || weight[P.x][P.y] + map[nx][ny] < weight[nx][ny]) {
					visited[nx][ny] = true;
					weight[nx][ny] = weight[P.x][P.y] + map[nx][ny];
					queue.add(new Pos(nx, ny));
				}
			}
		}
	}

	public static void init() {
		map = new int[N][N];
		weight = new int[N][N];
		visited = new boolean[N][N];
		MIN = Integer.MAX_VALUE;
	}
}

 

💡 결과

---