백준 1948 c++ "임계경로" -PlusUltraCode-

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

 

 

 

[필자 사고]

문제를 읽어보면 위상정렬과 백드래킹을 요구하는 문제이다.

 

이 문제에서 조심해야 될 점은 BFS탐색중 매 수행마다 Time[nextNum]의 기존값과 갱신값중 비교하여 

더 큰값을 넣어야 된다는 점이다.

 

또한 R_BFS() 에서 동일한 노드에 서로 다른 경로가 있을경우를 대비하여 visited를 사용해

이미 방문했으면 myQueue에 넣지 않고 방문 안했을 경우만 넣는 식으로 해야 된다.

 

1. 주요 변수 및 자료구조

• arr와 backArr는 각각 정방향 그래프와 역방향 그래프를 저장하는 2차원 벡터이다. arr[start]는 start 노드에서 갈 수 있는 다음 노드와 그 간선의 가중치(시간)를 저장하고, backArr[end]는 end 노드로 들어오는 이전 노드와 그 간선의 가중치를 저장한다.
• Time은 각 노드까지 도달하는 데 걸리는 최대 시간을 저장하는 벡터이다.
• D는 각 노드의 진입차수(In-degree)를 저장하는 벡터이다.
• N과 M은 각각 노드의 개수와 간선의 개수를 의미하며, startIdx와 endIdx는 시작 노드와 목표 노드를 나타낸다.
• resultCount는 목표 노드까지 도달하는 최장 경로에 포함된 간선의 수를 세는 데 사용된다.

2. 입력 처리 (Input 함수)

Input() 함수는 그래프 정보를 입력받고, 이를 바탕으로 arr, backArr, D 벡터를 초기화한다. 또한 시작 노드와 목표 노드를 입력받는다.

3. 위상정렬을 이용한 BFS (BFS 함수)

이 함수는 위상정렬을 사용하여 그래프의 각 노드에 도달하는 데 걸리는 최대 시간을 계산한다.

• 큐 myQueue를 사용하여 진입차수가 0인 노드를 처리한다.
• 현재 노드에서 갈 수 있는 다음 노드들의 진입차수를 감소시키며, 그 노드까지 도달하는 데 걸리는 최대 시간을 갱신한다.
• 진입차수가 0이 된 노드는 큐에 삽입하여 다시 처리된다.

4. 백트래킹을 이용한 역방향 BFS (R_BFS 함수)

이 함수는 목표 노드에서 시작하여 출발 노드로 거슬러 올라가며 최장 경로에 포함된 간선의 수를 센다.

• 큐 myQueue를 사용하여 목표 노드에서 출발한다.
• 현재 노드에 도달한 시간이 최장 시간일 때만 다음 노드로 이동한다.
• 백트래킹을 통해 방문하지 않은 노드들에 대해 경로를 추적하며, 최장 경로에 포함된 간선을 세는 방식이다.

5. 게임 시작 (GameStart 함수)

GameStart() 함수는 BFS()를 호출하여 각 노드에 도달하는 데 필요한 최대 시간을 계산한 후, R_BFS()를 호출하여 최장 경로에 포함된 간선의 수를 센다. 최종적으로 목표 노드까지 도달하는 데 걸린 시간과 간선의 수를 출력한다.

 

 

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <string>
#include <cstring>

using namespace std;

typedef pair<int, int> Node;

vector<vector<Node>> arr;
vector<vector<Node>> backArr;
vector<int> Time;
vector<int> D;
int N, M;
int startIdx, endIdx;


void Input() {
	cin >> N >> M;
	arr.resize(N + 1);
	backArr.resize(N + 1);
	D.resize(N + 1);
	Time.resize(N + 1);

	for (int i = 0; i < M; i++) {
		int start, end, time;
		cin >> start >> end >> time;
		arr[start].push_back({ end,time });
		backArr[end].push_back({ start,time });
		D[end]++;
	}

	cin >> startIdx >> endIdx;
}

void BFS() {
	queue<int> myQueue;
	myQueue.push(startIdx);

	while (!myQueue.empty()) {
		int nowNum = myQueue.front();
		myQueue.pop();

		for (Node nextNode : arr[nowNum]) {
			int nextNum = nextNode.first;
			int nextTime = nextNode.second;
			D[nextNum]--;
			Time[nextNum] = max(Time[nextNum], Time[nowNum] + nextTime);
			if (D[nextNum]==0) {
				myQueue.push(nextNum);
			}
		}
	}
}


int resultCount = 0;

void R_BFS() {
	queue<Node> myQueue;
	int maxTime = Time[endIdx];
	myQueue.push({endIdx,maxTime});
	vector<bool> visited;
	visited.resize(N + 1,false);
	visited[endIdx] = true;
	


	while (!myQueue.empty()) {
		int nowNum = myQueue.front().first;
		int nowTime = myQueue.front().second;
		myQueue.pop();

		for (Node nextNode : backArr[nowNum]) {
			int nextNum = nextNode.first;
			int nextTime = nextNode.second;

			if (nowTime - nextTime == Time[nextNum]) {
				resultCount++;
				if (visited[nextNum] == false) {
					myQueue.push({ nextNum,Time[nextNum] });
					visited[nextNum] = true;
				}
			}
		}
	}
}


void GameStart() {
	BFS();
	R_BFS();

	cout << Time[endIdx] << '\n';
	cout << resultCount;
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);

	Input();
	GameStart();
}