[BAEKJOON] 1738번 골목길

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

문제조건

1. 출발지부터 목적지까지 가야한다.
2. 단, 가는 경로에 깡패, 금품 두가지가 존재한다.
3. 목적지에 도착했을때, 금품의 양이 최대가 되는 경로를 구해라

접근방법

 

다익스트라로 푸는 최단경로 문제인가? 라고 생각이 들었는데, 깡패가 금품을 갈취하면 음의 정수로 바뀌기 때문에, 다익스트라 알고리즘에서는 최단경로라고 판단된 노드는 더이상 갱신하지 않지만, 금품을 계속 반복해서 갈취당하면 음의 무한대로 짧아질수 있기 때문에 위 알고리즘은 아니다. 생각해보니 예전에 배웠던 음의 가중치가 있을때 최단거리를 구할수 있는 Bellman-Ford 알고리즘이 생각났다.

Bellman-Ford 알고리즘

 

다익스트라 알고리즘과 더불어 최단경로를 구할 때 사용되는 대표적인 알고리즘이다.

차이점은 Bellman-Ford에서는 가중치가 음인것에 대해, 최단경로를 구할수 있고, 그 대신 전부 탐색해야하므로 시간적으로 O(n^3) 이고, 더 느리게 작동하는 알고리즘이란 점이다. 당연하지만 가중치가 모두 양수인 경우에도 이 알고리즘을 사용할수 있지만, 굳이 더 느린걸 사용할 필요는 없으니까 다익스트라를 사용하면 된다.

그러면 음의 가중치에 대한 그래프에서 무조건 최단경로를 탐색할 수 있는가?

대답은 No 이다. 특정한 경우에만 작동한다.

아래에 Bellman-Ford 알고리즘이 잘 동작하는 case는 무엇인지 나열해봤다.

1. 단순 음수 간선 : 가능
2. 사이클 존재, 양수값 > 음수값 : 사이클을 돈다고 해도, 더 작아지지 않으므로 가능하다.
3. 사이클 존재, 양수값 < 음수값 : 여기서 문제가 생긴다. 위에서 말한 계속해서 작아질수 있기때문이다. 

애초에 최단경로라는 정의가 끝이 있기때문에 값을 측정할 수있는것인데, 무한반복한다면 정의자체를 내릴수가 없다.

따라서 안되는 경우를 어떻게 판단하고 어떻게 동작하는지 과정을 살펴보자.

 

1. 시작노드 설정
2. 시작노드 거리 0 으로설정, 나머지 노드 거리 INF(무한대)로 설정
3. 현재 노드를 기준으로 연결된 모든 노드들 탐색, 최솟값 갱신
4. (3)과정을 모든 노드에 대해 수행
5. 모든 노드에 대해 알고리즘을 수행한 뒤, 한번 더 알고리즘을 수행했을때, 최소거리가 갱신된다면 음의 사이클이 있다는것.

---

이 문제는 Bellman-Ford 알고리즘을 정반대로 수행해주기만 하면된다!

테스트 케이스도 맞췄고, 로직도 전부 맞는거 같은데 대체 왜 이럴까,,,,,

이 부분에 대해서 예외케이스를 생각하는데 많은 시간을 썼다.

위 그림의 경우를 입력으로 넣어보자. 내가 결과를 예측할수 있게끔, 최대한 간단하게 그림을 그려봤다.

실행결과

결과로는 (출발) → 2 → (도착) 의 경로가 나와야 정상이다.

근데 위 예시는 왜 저런 결과를 내는가 보면, 나는 그냥 무조건 모든 정점을 기준으로 각각 한번씩 연결된 간선들을 전부 방문하면서 최댓값을 갱신한다는점이다. 그러면 위 그림에서도 당연히 노드4와 노드5 사이에 양의 사이클이 존재하므로 무조건 사이클은 존재한다고 컴퓨터가 판단한 것이다.

 

무슨 말이냐면 (출발) ~ (도착) 사이 경로에 아무 상관이 없는 노드들인데 결과에 영향을 준다는 점이다. 이 점에서 기존 코드에서 무조건적으로 양의사이클이 발생하면 -1을 출력하게 하는것이 아니라, 양의 사이클이 발생하더라도 출발노드와 도착노드와 연결이 되어있지 않으면 사이클이 없다고 판별하게끔 수정했다.

 

확인은 어떻게 하느냐? 지금 내 코드는 dist배열을 두고 거리를 구하고 있다. dist배열이 의미하는걸 잘 생각해보면 된다. dist배열은 출발지점부터의 거리이므로, -inf가 아닌 이상 출발점으로 부터 연결이 되어있다는 의미이다. 따라서 내가 알아야하는것은 도착점으로 부터의 연결이 되어있는지를 확인하면 된다. 나는 도착점부터 시작해서 BFS탐색방법으로 visited배열을 체크해줬다.

그래서 위 반례를 다시 입력으로 넣으니, 

굿!

?????????????????????????????????

뭘까 진짜,,,

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 이건 진짜 말그대로 삽질을 했다,,,,

memset / fill

 

나는 항상 memset()함수를 사용해서 2차원이상의 배열을 편하게 초기화해서 사용했다. 딱히 차이점도 몰랐고, 그냥 이렇게 초기화하기 편한 함수가 있구나 라고 생각을 했다.

• memset : void * memset( void * ptr, int value, size_t num)
  • ptr : 자료형의 시작포인터
  • value : 컨테이너에 채울 값
  • num : 몇개의 value를 채우는지

여기서 주목해야 하는점은 바로 value부분이다. 채울값을 인자로 주면 '아, 그렇구나~' 하고 그대로 컨테이너에 값을 채우는 것이아니라, unsigned char로 변환해서 삽입한다고 한다. 이게 무슨 말이냐면 char형의 크기는 알다시피 1Byte이다.

그러면 int(4Byte)의 경우에는 어떻게 될까? 여기서 문제가 발생한다. 1Byte를 강제로 4Byte에 맞추기 위해서 억지로 1Byte값을 4번 복사하게된다. 그래서 보통 초기화 할때 -1 혹은 0으로 초기화할때가 많았는데, 이 같은경우는 32비트 기준 이진수로 변환해보면

• -1 : 11111111 / 11111111 / 11111111 / 11111111
• 0 : 00000000 / 00000000 / 00000000 / 00000000 

이와 같은 값이 나오는데, char(문자)형 이외의 것들로 값을 준다면 직접 해보면 알겠지만, 복사하는 과정에서 전혀 다른 엉뚱한 값이 나온다. 

• fill : void fill (ForwardIt first, ForwardIt last, const T& value)

fill은 for문을 돌리는 것과 같이 동작해서 안전하게 동작한다.

 

fill	memset
느림	빠름
안전함	0, -1만 안전함
메모리 사용 그대로	불필요한 메모리 복사

 

결론은 0, -1 사용할때만 memset을 사용하는 것이고, 또한 복사를 통한 메모리 낭비가 있기 때문에 사이즈가 엄청큰 배열이 아니고서야 for문 쓰든가, fill함수 사용하는 것이 좋다라는 내용이고 실제로도 내 코드에서 memset부분을 fill로 바꿔주니 바로 초록불이 떴다,,!!

 

소스코드

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 101
using namespace std;

struct info {
	int n1, n2, w;
};
const int inf = 1e10;
int n, m, dist[MAX], path[MAX], visited[MAX];
bool cycle;
vector<info> edge;
vector<int> rev[MAX];

void bellmanford() {
	dist[1] = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < m; j++) {
			int n1 = edge[j].n1;
			int n2 = edge[j].n2;
			int w = edge[j].w;
			if (dist[n1] == -inf) continue;
			if (dist[n2] < dist[n1] + w) {
				// (n-1)번 반복 이후 다시 값이 갱신 된다면 cycle 존재
				// + 도착점과 이어져 있는 조건도 추가
				if (i == n && visited[n2]) cycle = true;
				dist[n2] = dist[n1] + w;
				path[n2] = n1;
			}
		}
	}
}

//DFS로 끝지점부터 첫지점 역으로 탐색후 출력
void trace(int num) {
	if (num == 1) {
		cout << 1 << " ";
		return;
	}
	trace(path[num]);
	cout << num << " ";
}

void judgeLink() {
	queue<int> q;
	//도착지점부터 이어져있는지 BFS 탐색 진행
	q.push(n);
	visited[n] = 1;
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int nxt : rev[cur]) {
			if (!visited[nxt]) {
				visited[nxt] = 1;
				q.push(nxt);
			}
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		edge.push_back({ u,v,w });
		rev[v].push_back(u);
	}
	judgeLink();
	fill(dist, dist + 101, -inf);
	bellmanford();
	if (cycle) cout << -1;
	else trace(n);
}

 

삽질의 연속,,, 이었다. ㅎㅇㅌ!!