https://programmers.co.kr/learn/courses/30/lessons/12978
코딩테스트 연습 - 배달 | 프로그래머스
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 이상 50 이하의 자연수입니다.
두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
a, b(1 ≤ a, b ≤ N, a != b)
[구하는 값]
1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.
[생각의 흐름]
1번 지역에서 인접한 곳으로 이동하며 지나온 거리를 증가시키다가, K를 넘으면 이동을 하지 않는 방법으로 푼다.
dfs,bfs 무엇을 써도 무방하다.
dfs로 하면 한 마을에 인접한 마을의 최대 수가 50인데 한번 방문한 곳은 방문하지 않기 때문에
시간복잡도는 50x49x48...=250만.
백트래킹시에 방문체크 해제를 하지 않아야 재방문을 피한다.
인접마을을 표현할 땐 인접배열과 인접리스트 중에서 인접리스트를 썼다.
a->b로 가는 경로가 여러개가 있을 수도 있기 때문이다. 인접배열을 쓴다면
[a][b]에는 가중치가 하나만 저장된다. (->사실 최소로 갱신하면 되는데 이땐 몰랐다)
그래서 인접리스트로 표현을 했고, dfs 탐색시에 방문했던 마을이라고 무조건 안가는 것이 아니라
그 방문체크값을 확인해서 이전보다 빠른 경로로 왔다고 판단될 때에만 그곳을 가도록 만든다.
그렇기때문에 탐색이 진행되기 위해선 방문체크값의 초기값은 큰 수이어야 하며
이러한 탐색 방식을 다익스트라라고 한다.
그렇게 기존에 방문한 비용에 비해 절약된 비용으로 다른 노드를 갈 수 있다는 것에 의미가 있다.
[코드]
import java.util.ArrayList;
import java.util.Arrays;
class Solution { //프로그래머스는 static으로 모두 선언해서 하지 않고 인스턴스 solution으로 돌리므로 다 인스턴스 변수여야 한다.
int ans=1; //즉 메인 만들어서 돌려볼때 인스턴스로 접근해야 한다는 뜻. 대신 메인에서 무슨 기능 넣으면 안됨,,초기지역도 포함해야되서 1로 시작
int visit[]=new int[51]; //전역변수 할거는 전역변수로!
int K,N;
ArrayList<ArrayList<int[]>> adj=new ArrayList<ArrayList<int[]>>();
public static void main(String[] args) {
int[][] arr= {
{1,2,1},{2,3,3},{5,2,2},{1,4,2},{5,3,1},{5,4,2}
};
Solution m=new Solution();
System.out.print(m.solution(5,arr,3));
}
public int solution(int N, int[][] road, int K) {
Arrays.fill(visit,Integer.MAX_VALUE); //수에 관한건 Integer에서, 배열 관련한 함수는 Arrays에!
this.N=N;
this.K=K;
for(int i=0;i<51;i++)
adj.add(new ArrayList<int[]>()); //이중어레 초기화 필요
for(int i=0;i<road.length;i++) {
adj.get(road[i][0]).add(new int[]{road[i][1],road[i][2]}); //int[]는 Integer처럼 쓰인다
adj.get(road[i][1]).add(new int[]{road[i][0],road[i][2]});
}
dfs(1,0);
return ans;
}
public void dfs(int cur,int len) {
visit[cur]=len;
for(int[] nx:adj.get(cur)) {
if(nx[1]+len>K||visit[nx[0]]<nx[1]+len) //다익스트라. 같은 지점 간다면 더 짧을때만 갈 수 있다.
continue; //왜냐?a~b사이 가중치 여러개 있을 수 있어서 가봤다고 아예 안가면 안됨
if(visit[nx[0]]==Integer.MAX_VALUE) //0이 안갔단 표시가 아님
ans++;
dfs(nx[0],nx[1]+len);
}
}
}
'PS' 카테고리의 다른 글
| 백준 17349 1루수가 누구야 (0) | 2019.08.14 |
|---|---|
| 백준 17090 미로 탈출하기 (0) | 2019.08.14 |
| 백준 13251 조약돌 꺼내기 (0) | 2019.08.13 |