[프로그래머스] GPS (2017 카카오코드 본선)

문제 링크 : programmers.co.kr/learn/courses/30/lessons/1837

 

 

DP문제이다.

 

<전체적인 알고리즘>

1. 시간을 1씩 증가시키며 1~n까지의 노드가 오는 경우를 생각하며 d[시간][현재 노드]배열에 저장을 한다.

   (즉 d[시간][현재 노드]는  현재 시간에 현재 노드가 위치할 수 있는 경우 중 최소의 수정 횟수가 저장되어 있다.

2. t를 끝까지 증가시키며 목적지의 값을 구한다.

 

 

점화식 : D[i][j] = min(D[i - 1][인접 노드], D[i - 1][j]) + (현재노드와 log의 노드가 다르면 +1 아니면 +0)

 

<전체 코드>

#include<iostream>
#include <vector>
#include<algorithm>

using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, int m, vector<vector<int>> edge_list, int k, vector<int> gps_log) {
    
    int d[102][203];  //i번째 j노드
    vector<int> a[203];
	for (int i = 0; i < edge_list.size(); i++)    //그래프 만들기
	{
		int n1 = edge_list[i][0];
		int n2 = edge_list[i][1];

		a[n1].push_back(n2);
		a[n2].push_back(n1);
	}

	fill(&d[0][0], &d[100][202], 987654321);
	d[0][gps_log[0]] = 0;

	for (int i = 1; i <= k-1; i++)
	{
		for (int j = 1; j <= n; j++)
		{   
			for (int z = 0; z < a[j].size(); z++)    //인접해 있는(올 수 있는) index중 최솟값 구하기
			{
				int next = a[j][z];
				d[i][j] = min(d[i - 1][next], d[i][j]);
			}
			d[i][j] = min(d[i - 1][j], d[i][j]);   //그대로 가만히 노드에 있는 경우도 포함
			if (gps_log[i] != j)d[i][j] += 1;   // 현재와 다른 노드면 +1
		}
	}
  
    int answer=d[k-1][gps_log[k-1]]; //목적지가 gps_log[k-1]일 때 수정하는 최솟값
    if(answer >= 987654321)
    {
        answer = -1;
    }
	return answer;
}

 

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.