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

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

SW Expert Academy

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import javax.sound.midi.Soundbank;

public class CodingTest {
	static int N;
	static int[][] map;
	static int[] dx = { 0, 1, 0, -1 };
	static int[] dy = { 1, 0, -1, 0 };
	static int[][] sum;
	static int[][] visited;
	static int min_time;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			map = new int[N][N];
			sum = new int[N][N]; // 합계
			visited = new int[N][N];
			min_time = Integer.MAX_VALUE;
			for (int i = 0; i < N; i++) { // 정보 저장
				String str = sc.next();
				for (int j = 0; j < N; j++) {
					map[i][j] = str.charAt(j) - '0';
					sum[i][j] = Integer.MAX_VALUE;
				}
			}

			sum[0][0] = 0;
			visited[0][0] = 1;
			find(0, 0);
			System.out.println("#" + test_case + " " + min_time);
		}
	}

	public static void find(int x, int y) {
		if (x == N - 1 && y == N - 1) { // 도착점
			min_time = Math.min(sum[x][y], min_time); // 최저값
			return;
		}
		if (min_time <= sum[x][y])
			return; // 현재의 최소값보다 클 때
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < N && ny >= 0 && ny < N) { // 범위 안에 있을 때 + 방문 안했을 때
				if (visited[nx][ny] == 0 || sum[x][y] + map[nx][ny] < sum[nx][ny]) { // 방문 안했거나 더 작은 값일 때
					sum[nx][ny] = sum[x][y] + map[nx][ny]; // 총 합계 저장
					visited[nx][ny] = 1; // 방문 처리
					find(nx, ny);
				}
			}
		}
	}

}

처음에 visited[nx][ny] == 0 && sum[x][y] + map[nx][ny] < sum[nx][ny] 로 적었다가 한참 헤맸다. 방문했어도 더 작은 값이면 처리해줘야 한다.