문제 링크

문제 간단 해석

시작부분부터 정해진 길을 따라 특정 마을까지 갈 수 있는지 없는지를 확인한다.

Java

Map.Entry를 이용하여 PriorityQueue를 구축했다.

풀이 코드

import java.util.*;

class Solution {
    private Map<Integer, Map<Integer, Integer>> map = new HashMap<>();

    public void mapAdd(int now, int to, int time) {
        if (!map.containsKey(now))
            map.put(now, new HashMap<>());

        if (!map.get(now).containsKey(to))
            map.get(now).put(to, time);
        else
            map.get(now).put(to, Math.min(map.get(now).get(to), time));
    }

    public int solution(int N, int[][] road, int K) {
        boolean[] check = new boolean[N + 1];

        for (int[] r: road)
            for (int i = 0; i < 2; i++)
                mapAdd(r[i], r[1-i], r[2]);

        Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Map.Entry.comparingByValue());
        queue.add(new HashMap.SimpleEntry<>(1, 0));
        Map.Entry<Integer, Integer> entry;
        int answer = 0, now, taken, to, time;

        while (!queue.isEmpty()) {
            entry = queue.remove();
            now = entry.getKey();
            taken = entry.getValue();

            if (check[now])
                continue;

            check[now] = true;
            answer++;

            for (Map.Entry<Integer, Integer> newEntry: map.get(now).entrySet()) {
                to = newEntry.getKey();
                time = newEntry.getValue();

                if (!check[to] && time + taken <= K)
                    queue.add(new HashMap.SimpleEntry<>(to, time + taken));
            }
        }

        return answer;
    }
}

해석

public void mapAdd(int now, int to, int time) {
    if (!map.containsKey(now))
        map.put(now, new HashMap<>());

    if (!map.get(now).containsKey(to))
        map.get(now).put(to, time);
    else
        map.get(now).put(to, Math.min(map.get(now).get(to), time));
}

map에 현재 마을 정보가 없다면 추가한다.
map의 현재 마을 내에 목표 마을 정보가 없다면 추가한다.
목표 마을 정보가 있다면, 목표 마을로 갈 수 있는 시간 정보를 최솟값으로 유지하도록 한다.

for (int[] r: road)
    for (int i = 0; i < 2; i++)
        mapAdd(r[i], r[1-i], r[2]);

위에 설명한 mapAdd 함수를 통해, 한 마을에서 다른 마을로 갈 수 있는 길을 기록한다.

Queue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Map.Entry.comparingByValue());

Map.entry를 담을 우선순위 큐를 선언한다. 해당 큐의 비교 기준은 Entry 내 value값 오름차순이다.

while (!queue.isEmpty()) {
    entry = queue.remove();
    now = entry.getKey();
    taken = entry.getValue();

    if (check[now])
        continue;

    check[now] = true;
    answer++;

    for (Map.Entry<Integer, Integer> newEntry: map.get(now).entrySet()) {
        to = newEntry.getKey();
        time = newEntry.getValue();

        if (!check[to] && time + taken <= K)
            queue.add(new HashMap.SimpleEntry<>(to, time + taken));
    }
}

queue 값을 가져와 이미 방문이 끝난 곳인지 확인한다. 현재 우선순위 큐는 빠른 시간 내에 도착할 수 있는 곳을 먼저 가져오므로, 뒤늦게 값을 가져왔다는 것은 이전에 방문한 시간보다 같거나 오래 걸렸다는 뜻이다. 따라서 연산하지 않는다.

해당 마을에서 다시 찾아갈 수 있는 곳을 찾는다. 만약 그 곳이 방문하지 않은 곳이며 제한시간 안에 방문이 가능하다면, queue에 넣는다.

Python

엄청 옛날에 짠 것 같다.

풀이 코드

def solution(N, road, K):
    field = [{} for _ in range(N + 1)]
    total_dis = [N * 10000] * (N + 1)
    total_dis[1] = 0
    check = [True] * (N + 1)
    check[1] = False
    for n1, n2, dis in road:
        try:
            if field[n1][n2] > dis:
                field[n1][n2] = dis
                field[n2][n1] = dis
        except:
            field[n1][n2] = dis
            field[n2][n1] = dis

    stack = [1]
    while stack:
        to = 0
        now = stack[-1]
        min_dis = N * 10000
        for i in field[now].keys():
            if total_dis[i] > total_dis[now] + field[now][i]:
                total_dis[i] = total_dis[now] + field[now][i]
        for i in range(2, N + 1):
            if check[i] and min_dis > total_dis[i]:
                to = i
                min_dis = total_dis[i]

        if not to:
            stack.pop()
            break
        check[to] = False
        stack.append(to)

    return len([x for x in total_dis if x <= K])

해석

for n1, n2, dis in road:
    try:
        if field[n1][n2] > dis:
            field[n1][n2] = dis
            field[n2][n1] = dis
    except:
        field[n1][n2] = dis
        field[n2][n1] = dis

field 내 마을간의 거리를 최소로 한다.

while stack:
    to = 0
    now = stack[-1]
    min_dis = N * 10000
    for i in field[now].keys():
        if total_dis[i] > total_dis[now] + field[now][i]:
            total_dis[i] = total_dis[now] + field[now][i]
    for i in range(2, N + 1):
        if check[i] and min_dis > total_dis[i]:
            to = i
            min_dis = total_dis[i]

    if not to:
        stack.pop()
        break
    check[to] = False
    stack.append(to)

현재 위치에서 갈 수 있는 길이 있다면 그 값을 최소화한다.
그 후 최소 시간으로 갈 수 있는 곳을 찾는다.
찾지 못했다면 stack에서 없앤다.
찾았다면 stack에 넣어주어 그곳으로 이동한 효과를 가진다.

여담

Python 코드는 그닥 좋지 못하다. Java 코드를 참조하자.
근데 사실 Java도 Map.Entry 써보겠다고 이것저것 시도한거라..
우선순위 큐(Python에서는 heapq)를 사용한다는 점만 착안하자.