(코테) 프로그래머스_경주로 건설 *백트레킹, 완전탐색

문제 링크

 

https://school.programmers.co.kr/learn/courses/30/lessons/67259?language=java

 

 

 

 

 

 

 

내가 기존에 구상한 답 (시간초과)

import java.util.*;

class Solution {
    int[] nx = {-1, 1, 0, 0};
    int[] ny = {0, 0, -1, 1};    

    int resultMin = Integer.MAX_VALUE;

    public int solution(int[][] board) {
        Map<String, Boolean> map = new HashMap<>();
        dfs(map, board, 0, 0, -1, 0);                
        return resultMin;
    }

    public void dfs(Map<String, Boolean> map, int[][] board, int x, int y, int ref, int fee) {
        int len = board.length;

        // 도착 지점
        if (x == len - 1 && y == len - 1) {
            resultMin = Math.min(resultMin, fee);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + nx[i];
            int nextY = y + ny[i];

            if (nextX < 0 || nextY < 0 || nextX >= len || nextY >= len) continue;
            if (board[nextX][nextY] == 1) continue;

            String key = nextX + "," + nextY + "," + i;
            if (map.containsKey(key) && map.get(key)) continue;

            map.put(key, true);

            int nowLine = (i == 0 || i == 1) ? 1 : 2;
            int nextFee = (ref == -1 || ref == nowLine) ? fee + 100 : fee + 600;

            dfs(map, board, nextX, nextY, nowLine, nextFee);

            map.put(key, false); // 백트래킹
        }
    }
}

 

 

 

 

정석 답

import java.util.*;

class Solution {
    int[] nx = {-1, 1, 0, 0};
    int[] ny = {0, 0, -1, 1};    

    int resultMin = Integer.MAX_VALUE;

    public int solution(int[][] board) {
        Map<String, Integer> visited = new HashMap<>();
        dfs(visited, board, 0, 0, -1, 0);                
        return resultMin;
    }

    public void dfs(Map<String, Integer> visited, int[][] board, int x, int y, int ref, int fee) {
        int len = board.length;

        // 종료 조건
        if (x == len - 1 && y == len - 1) {
            resultMin = Math.min(resultMin, fee);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int nextX = x + nx[i];
            int nextY = y + ny[i];

            // 범위 초과, 벽
            if (nextX < 0 || nextY < 0 || nextX >= len || nextY >= len) continue;
            if (board[nextX][nextY] == 1) continue;

            int nowLine = (i == 0 || i == 1) ? 1 : 2;
            int nextFee = (ref == -1 || ref == nowLine) ? fee + 100 : fee + 600;

            String key = nextX + "," + nextY + "," + i;

            // 이미 더 싸게 도달한 적 있다면 skip
            if (visited.containsKey(key) && visited.get(key) <= nextFee) continue;

            visited.put(key, nextFee);
            dfs(visited, board, nextX, nextY, nowLine, nextFee);
        }
    }
}

 

 

회고.

1.visted 배열로 방문처리 (기존 백트레킹) -> map으로 좌표 + 방향 + 다음 도착지?의 비용 총 4개 비교 필요 (위 문제 )

2. 다음 도착위치의 비용까지 기억을해서 불필요한 방문을 최소화 시킨다는게 이 문제의 특색인거 같음. 

나머지는 기존 dfs +  백트레킹 문제 유형과 비슷, 까다로운 예외 조건도 많이 없었으며....