[SWEA] 보급로

👀 문제 설명

문제

로그인해야 문제를 볼 수 있다.

 

✍🏻풀이

BFS를 사용해 풀었다.

 

map[i][j]에는 각 칸의 복구 작업을 저장하고, minTime[i][j]는 각 칸까지의 최소 복구 작업 시간을 저장한다.

 

Deque을 사용해서 BFS를 구현하면 된다.

가장 초기에는 시작점 (0, 0)을 덱에 넣는다. 덱이 빌 때까지 덱의 원소에 하나씩 접근한다.

현재 칸은 int[] cur이고, 인접한 칸(이동할 수 있는 칸)은 nextX, nextY라고 한다.

minTime[cur[0]][cur[1]] + map[nextX][nextY]가 minTime[nextX][nextY]보다 작을 경우, 답이 될 수 있으므로, minTime[nextX][nextY]를 minTime[cur[0]][cur[1]] + map[nextX][nextY]로 바꾸고, (nextX, nextY)를 덱에 넣는다.

-> 반복

 

코드

package swea;

// 보급로 (https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE&problemTitle=%EB%B3%B4%EA%B8%89%EB%A1%9C&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 )

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

public class SWEA_1249 {
	
	private static int N;
	private static int[][] map;
	private static int[][] minTime;
	private static int[] dx = { -1, 0, 1, 0 };
	private static int[] dy = { 0, 1, 0, -1 };
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T;

		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			// input
			N = Integer.parseInt(br.readLine());
			map = new int[N][N];
			minTime = new int[N][N];
			
			for (int i = 0; i < N; i++) {
				String str = br.readLine();
				
				for (int j = 0; j < N; j++) {
					map[i][j] = str.charAt(j) - '0';
					minTime[i][j] = Integer.MAX_VALUE;
				}
			}
			
			// solve
			bw.write("#" + tc + " " + getAns() + "\n");
		}

		bw.flush();
		bw.close();
	}
	
	private static int getAns() {
		Deque<int[]> queue = new ArrayDeque<>();
		queue.offer(new int[] { 0, 0 }); // 시작점
		minTime[0][0] = 0;
		
		while (!queue.isEmpty()) {
			int[] cur = queue.poll();
			
			for (int dir = 0; dir < 4; dir++) {
				int nextX = cur[0] + dx[dir];
				int nextY = cur[1] + dy[dir];
				
				if (nextX < 0 || nextX >= N || nextY < 0 || nextY >= N) continue;
				
				if (minTime[cur[0]][cur[1]] + map[nextX][nextY] < minTime[nextX][nextY]) {
					minTime[nextX][nextY] = minTime[cur[0]][cur[1]] + map[nextX][nextY];
					queue.offer(new int[] { nextX, nextY });
				}
			}
		}
		
		return minTime[N - 1][N - 1];
	}

}