SW Expert Academy] 1249 D4 보급로

SW Expert Academy] 1249 D4 보급로

---

언어 : Java

풀이 방법 : DFS + BackTracking + Memoization

URL : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15QRX6APsCFAYD&categoryId=AV15QRX6APsCFAYD&categoryType=CODE

SW Expert Academy

 

간단한 문제 설명

N x N 이차원 배열이 주어질 때 0,0에서부터 N-1, N-1까지 최소 비용을 들여 도착하는 문제이다. (N은 최대 100) 

 

풀이 과정

결국 Brute Force(완전 탐색) 문제이다. 모든 가는 길의 경우의 수를 다 해봐야하는 문제이기 때문에 DFS로 구현하려했다.

DFS로만 구현하면 시간초과가 났다.

그래서 BackTracking을 더했더니 여전히 시간초과가 났다.

그래서 Memoization을 더했다! 근데 여전히 10번 테스트케이스에서 시간초과가 나더라!ㅠㅠ

 

그 원인은... DFS 할 때 사방탐색을 '상, 하, 좌, 우' 로 탐색했다는 것....

사방탐색을 '하, 우, 상, 좌' 로 바꾸니까 PASS되더라..!

 

여태 문제 풀면서 생각해보지 못했다. 어떤 알고리즘 기법이 아닌 '야성'으로 더 효율적인 방법을 찾아내는 '통찰력'을 요하는 문제인가.. 라는 생각이 들었다.

 

소스코드

 

package Jan2020;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Solution_1249_D4_보급로 {
 
    private static int N, ans = Integer.MAX_VALUE;
    private static char[][] arr;
    private static int[][] memo;
//    private static int[] dr = { -1, 1, 0, 0 }; // dfs로 풀 때 상하좌우로 탐색하면 터지더라!!
//    private static int[] dc = { 0, 0, -1, 1 };
    private static int[] dr = { 1, 0, -1, 0 }; // 하 우 상 좌로 탐색해야 안터진다.
    private static int[] dc = { 0, 1, 0, -1 };
    private static boolean[][] visited;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
        int T = Integer.parseInt(in.readLine());
 
        for (int t = 1; t <= T; t++) {
            N = Integer.parseInt(in.readLine()); // 배열 사이즈
 
            arr = new char[N][N];
            visited = new boolean[N][N];
            ans = Integer.MAX_VALUE;
            memo = new int[N][N];
 
            for (int i = 0; i < N; i++) {
                arr[i] = in.readLine().toCharArray();
            }
 
            // 시작점 0,0
            // 도착점 N-1,N-1
            visited[0][0] = true;
            dfs(0, 0, 0);
 
            System.out.println("#" + t + " " + ans);
        }
 
    }
 
    private static void dfs(int i, int j, int sum) {
        if (ans <= sum) // 찾은 최소값보다 현재 sum이 크면 그 경로는 더 이상 탐색 필요 없음
            return;
 
        if (i == N - 1 && j == N - 1) { // 목적지에 도착했으면
            if (ans > sum)
                ans = sum;
            return;
        }
 
        // Memoization
        if (memo[i][j] == 0)
            memo[i][j] = sum;
        else {
            if (memo[i][j] > sum)
                memo[i][j] = sum;
            else
                return;
        }
 
        for (int k = 0; k < 4; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];
 
            if (nr >= 0 && nc >= 0 && nr < N && nc < N && !visited[nr][nc]) {
                visited[nr][nc] = true;
                dfs(nr, nc, sum + (arr[nr][nc] - '0'));
                visited[nr][nc] = false;
            }
        }
 
    }
 
}