https://programmers.co.kr/learn/courses/30/lessons/12978?language=java
코딩테스트 연습 - 배달
5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4
programmers.co.kr
문제 설명
N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.
위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.
마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.
제한사항
- 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
- road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
- road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
- road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
- a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
- 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
- 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
- K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
- 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
- 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.
풀이코드
import java.util.*;
class route{
int now;
boolean[][] visitied;
int time;
public route(int now, int N, int time) {
this.now = now;
this.visitied = new boolean[N+1][N+1];
this.time = time;
}
public route(int now, boolean[][] v, int time) {
this.now = now;
this.visitied = v;
this.time = time;
}
}
class Solution {
public int solution(int N, int[][] road, int K) {
int answer = 0;
int[][]map = new int[N+1][N+1];
for(int[] r : road) {
if(map[r[0]][r[1]]==0 || map[r[0]][r[1]] > r[2]) {
map[r[0]][r[1]] = r[2];
map[r[1]][r[0]] = r[2];
}
}
Queue<route> q = new LinkedList<route>();
int[] ans = new int[N+1];
for(int i = 0; i<= N; i++) {
ans[i] = Integer.MAX_VALUE;
}
ans[1] = 0;
q.offer(new route(1,N,0));
while(!q.isEmpty()) {
route r = q.poll();
int n = r.now;
int k = r.time;
for(int i = 1; i<= N ; i++) {
if(!r.visitied[n][i]&&map[n][i]!=0 && map[n][i]+k<=K && ans[i]>map[n][i]+k) {
boolean[][] v = new boolean[N+1][N+1];
for(int j = 1; j<= N ; j++) {
System.arraycopy(r.visitied[j], 0, v[j], 0, N+1);
}
v[n][i] = true;v[i][n]=true;
ans[i] =map[n][i]+k;
q.offer(new route(i,v,map[n][i]+k));
}
}
}
for(int i =1; i<=N; i++) {
if(ans[i]<=K)answer++;
}
return answer;
}
}알고리즘 풀이를 안하다 보니 하나하나 너무 어렵다
그래프에서 최소 거리를 구하는 알고리즘이 때문에, 하나의 route라는 방문 경로를 담은 class를 하나 선언해 주었다.
route라는 클래스에는 시작점인 now와 길을 가면서 얼마나 걸렸을 지를 담을 time, 그리고 재방문 여부를 판단할 visitied배열이 있다.
solution에 들어오는 값은 N, road, K이렇게 세개의 값이 들어오게 된다.
N이 그래프의 꼭지점 이므로,
연결 배열으로 이용할 map[N+1][N+1]을 선언해준다.
그리고 들어오는 road에서 값을 뽑아서 그래프간의 연결을 표현해준다.
문제 설명을 보면, 같은 길이지만 걸리는 시간이 다른 길들이 있다. 그렇기에
map에 road의 값을 넣으면서, 원래 가지고 있는 값과 비교하면서 제일 작은 수가 들어가 하나만 남기게 한다. 어짜피 최소값으로 계산해야 하기떄문에 시간이 오래 걸리는 route는 무시한다.
그리고 BFS를 돌기 위해 Queue를 선언해준다.
Queue에는 아까 선언했던 route클래스를 넣는다.
그리고 이 부분이 중요한데, 이 부분을 이용하느냐 아니냐에 따라서 32번 테스트 케이스가 시간초과가 나고 안나고가 결정된다.
최솟값을 넣어서 이 값을 기준으로 계산을 이어나갈 수 있도록 ans에 가장 1에서 부터 도착점까지 가장 최소 시간을 계산해 준다.
이미 방문을 한 값들을 그냥 바로 처리하는 PriorityQueue를 쓰는 방법도 있지만, 오랫만에 푸니까 comparator를 선언하기 번거로워서 그냥 이렇게 따로 갑을 처리해 주었다. (그리고 이게 더 빠르지 않을까?)
Queue에 첫번쨰 1부터 시작할 값을 넣어주고, 반복문while을 통해서 BFS를 돌린다.
먼저, q에서 값 하나를 빼고, 이 값을 시작점 n과, 걸린시간 k를 뺴준다.
그리고 map에 있는 값을 통해서 연결되어 있는 값 중에서 이전에 방문하지 않았던 길을 통해서 계산을 이어간다.
1부터.. (2부터 돌껄) N까지 값을 돌면서, 방문하지 않았고(!r.visitied[n][i]) , 연결되어 있으며(map[n][i]!=0), K보다 걸리는 시간이 작고(map[n][i]+k<K) , 가장 최단거리인(ans[i]>map[n][i]+k) 값을 찾는다.
BFS이므로 각각의 방문기록은 모두 복사해서 처리해 주어야 한다. boolean[][]로 선언했던 값을
System.arraycopy()로 복사해준다.
그리고 나서 새로 선언된 값에 방문 처리를 해준다.
그 다음에 이제 ans에 값도 최소값으로 update해주고, q에도 방문했던 값을 넣어준다.
그리고 K보다 작은 방문 가능한 도시들을 모두 answer++로 카운트해주면된다.
사실 효율적으로 풀이했다는 생각은 들지 않기는 하지만, 맞춘게 중요하지