[BOJ / 메모이제이션 BFS] 2157 여행

https://www.acmicpc.net/problem/2157

2157번: 여행

 

2157 여행

알고리즘 : 메모이제이션 / BFS

기본적인 메모이제이션을 이용한 BFS 풀이입니다. 인접리스트를 이용하여 각 도시간 항로를 만드는데 도착지가 출발지보다 작은 경우는 추가하지 않습니다. (시간 절약)

메모이제이션 테이블은 DP[A][B]=K를

 

                                                              - A : 현재까지 들린 도시의 수

                                                              - B : 현재 도시 번호

                                                              - K : 최대 기내식 점수 합

 

으로 하여 처리합니다. 정답률에 비해 쉬운 문제였습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

< CODE >

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

using namespace std;

#define MAX 305

struct forQ
{
	int cur;
	int cnt;
	int score;
};

int dp[MAX][MAX];

vector<pair<int,int>> inj[MAX];
queue<forQ> q;
int result = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n, m, k;

	cin >> n >> m >> k;
	
	for (int i = 0; i < k; i++)
	{
		int s, e, p;

		cin >> s >> e >> p;

		if (e > s)
			inj[s].push_back({ e,p });
	}

	q.push({1,1,0});

	while (!q.empty())
	{
		forQ now = q.front(); q.pop();

		if (now.score < dp[now.cnt][now.cur])
			continue;

		if (now.cur == n && now.cnt <= m)
		{
			result = max(result, now.score);
			continue;
		}

		for (int i = 0; i < inj[now.cur].size(); i++)
		{
			pair<int,int> to = inj[now.cur][i];

			if (to.first != n && now.cnt + 1 == m)
				continue;

			if (now.score + to.second > dp[now.cnt + 1][to.first])
			{
				dp[now.cnt + 1][to.first] = now.score + to.second;
				q.push({ to.first, now.cnt + 1, now.score + to.second });
			}
		}
	}

	cout << result << '\n';

	return 0;
}

시간 : 36ms

 

태그 : #BOJ 여행 #백준 여행 #2157 여행 #여행 풀이