[Programmers] 배달(Python, Java)

문제

요약

마을 1에서 k시간 내로 배달할 수 있는 마을의 개수를 구해라.

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12978?language=python3#

프로그래머스

---

풀이

Python

처음 풀이는 방문배열을 0으로 뒀는데, K+1로 두고 비교 해준 것이 더 편리한 것 같다.

from collections import deque
def solution(N, road, K):
    answer = set([1])
    q = deque([1])
    
    visited = [K+1] * (N+1)
    visited[1] = 0
    arr = [[] for _ in range(N+1)]
    
    for i in range(len(road)):
        x, y, s = road[i]
        if x not in arr[y]:
            arr[x].append((y, s))
            arr[y].append((x, s))
    
    while q:
        now = q.popleft()
        for i, s in arr[now]:
            if visited[i] > visited[now] + s:
                answer.add(i)
                q.append(i)
                visited[i] = visited[now] + s
    
    return len(answer)

 

 

Java

자바로 바꿔서 푸는 데 2차원 배열에 append해주는 것부터 막혀서 gpt한테 물어보면서 풀었다. 어려웡ㅠㅜ

배운 것

1. 자바의 Set은 HashSet으로 구현

2. 자바의 Queue는 LinkedList로 구현

3. 2차원 배열 안의 값도 (key, value)로 채울 거라면, 그것도 정의해줘야 함.

4. 2차원 배열 1차원 ArrayList로 만들어 두고, 반복문으로 크기만큼 ArrayList 추가해주기

5. isEmpty로 비었는지 확인, poll은 첫번째 요소 빼기

 

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        Set<Integer> answer = new HashSet<>();
        Queue<Integer> q = new LinkedList<>();
        
        int[] visited = new int[N+1];
        Arrays.fill(visited, K+1);
        visited[1] = 0;
        List<List<int[]>> arr = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            arr.add(new ArrayList<>());
        }
        
        for (int[] r : road) {
            int x = r[0];
            int y = r[1];
            int s = r[2];
            if (!arr.get(y).contains(x)) {
                arr.get(x).add(new int[]{y, s});
                arr.get(y).add(new int[]{x, s});
            }
        }
        
        q.add(1);
        answer.add(1);
        
        while (!q.isEmpty()) {
            int now = q.poll();
            for (int[] next : arr.get(now)) {
                int i = next[0];
                int s = next[1];
                if (visited[i] > visited[now] + s) {
                    answer.add(i);
                    q.add(i);
                    visited[i] = visited[now] + s;
                }
            }
        }
        
        return answer.size();
    }
}