프로그래머스 GPS
코드
#include <vector>
#include <algorithm>
#include <iostream>
#define INF 1e9
using namespace std;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
int answer = 0;
vector<int> graph[201];
for (auto i : edge_list) {
graph[i[0]].push_back(i[1]);
graph[i[1]].push_back(i[0]);
}
for(int i=1;i<=n;i++) graph[i].push_back(i);
vector<vector<int>> dp(k, vector<int>(n + 1, INF));
dp[0][gps_log[0]] = 0;
for (int i = 0; i < k - 1; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][j] == INF) continue;
for (int k : graph[j]) {
int re = dp[i][j];
if (gps_log[i + 1] != k) re++;
dp[i + 1][k] = min(dp[i + 1][k], re);
}
}
}
answer = dp[k - 1][gps_log[k - 1]];
if(answer==INF) return -1;
return answer;
}
풀이
먼저 인접리스트 방식으로 그래프를 구현해줬습니다
vector<int> graph[201];
for (auto i : edge_list) {
graph[i[0]].push_back(i[1]);
graph[i[1]].push_back(i[0]);
}
for(int i=1;i<=n;i++) graph[i].push_back(i);
문제에서 노드는 그 자리에 머무를 수도 있기 때문에 리스트에 자기 자신의 노드도 포함시켜주는 것이 뽀인트입니다.
dp테이블을 만들고 무한으로 초기화 시켜줬습니다 dp에는 오류회수가 저장 되는데 처음 시작점은 0으로 초기화 해줍니다
dp테이블을 돌면서 값을 갱신해주는데 현재 값이 INF라면 넘깁니다 무한이 아니라면 현재 노드와 연결된 곳들을 다 체크하면서 만약 gps_log의 현재 시간과 같은 값이라면 오류값을 추가하지 않고 그대로 가져오고 다르다면 +1을 해주면서 채워주면 됩니다.
Author And Source
이 문제에 관하여(프로그래머스 GPS), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@josajang98/GPS저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)