[ 백준 1865 ] 웜홀 (C++)

 

 

 

1865번: 웜홀

 

문제!

---

때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다.

시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라.

 

---

요약하면

int N, M, W; // n개 지점 , m개 도로, w개 웜홀

// 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로   + 시간이 뒤로 감


//출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지? 출력

 

 

또다시 길찾기 문제... 

이번엔 - 간선도 존재하여 좀 까다롭다고 생각 했으나

한 지점에서 모든 지점을 탐색하고 역으로 모든지점에서 한 지점으로 향하게끔 하는 방법.... 

며칠전에 풀었던 문제에서 다익스트라 알고리즘을 통해 역으로 탐색한 점이 생각나 다익스트라로 구현해 보았습니다.

 

하지만 실패.. 

 

실패 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <deque>
#include <queue>
#include <deque>
using namespace std;

int T;

int N, M, W; // n개 지점 , m개 도로, w개 웜홀

// 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로   + 시간이 뒤로 감


//출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지? 출력

vector<pair<int,int>>city[501];  // 정방향
vector<pair<int, int>>revcity[501]; // 역방향

vector<int>distList(501,987654321);
vector<int>redistList(501, 987654321);


void dijkstra(int start,int mode) {

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Temp;
	distList[start] = 0;
	Temp.push({ 0,start });
	while (!Temp.empty()) {
		int startind = Temp.top().second;
		int distance = Temp.top().first;
		Temp.pop();

		if (mode == 1) {
			for (int i = 0; i < city[startind].size(); i++) {
				int Tempind = city[startind][i].second;
				int Tempdist = city[startind][i].first;

				if (Tempdist + distance < 0) {
					distList[Tempind] = Tempdist + distance;
				}

				if (distList[Tempind] > Tempdist + distance) {
					distList[Tempind] = Tempdist + distance;
					Temp.push({ distList[Tempind] , Tempind });
				}
			}
		}
		else {
			for (int i = 0; i < revcity[startind].size(); i++) {
				int Tempind = revcity[startind][i].second;
				int Tempdist = revcity[startind][i].first;
				if (Tempdist + distance < 0) {
					redistList[Tempind] = Tempdist + distance;
				}
				if (redistList[Tempind] > Tempdist + distance) {
					redistList[Tempind] = Tempdist + distance;
					Temp.push({ redistList[Tempind] , Tempind });
				}
			}
		}
	}
}


void allReset() {

	for (int i = 1; i <= N; i++) {
		distList[i] = 987654321;
		redistList[i] = 987654321;
		city[i].clear();
		revcity[i].clear();
	}
}


int main() {
	cin >> T;

	while (T--) {
		
		cin >> N >> M >> W;
		allReset();



		int tempStart, tempEnd, tempTime;
		
		for (int i = 1; i <= M; i++) { // 
			cin >> tempStart >> tempEnd >> tempTime;
			city[tempStart].push_back({tempTime, tempEnd});
			city[tempEnd].push_back({ tempTime, tempStart });

			revcity[tempStart].push_back({ tempTime, tempEnd });
			revcity[tempEnd].push_back({ tempTime, tempStart });
		}

		for (int i = 1; i <= W; i++) {
			cin >> tempStart >> tempEnd >> tempTime;
			city[tempStart].push_back({tempTime*(-1), tempEnd});
			revcity[tempStart].push_back({ tempTime * (-1), tempEnd });
		}

		dijkstra(1, 1);
		//dijkstra(1, 0);


		if (distList[1] < 0) {
			cout << "YES" << endl;
		}
		else {
			cout << "NO" << endl;
		}

	}


	return 0;
}

다익스트라로 1~ 모든지점 , 모든지점에서 ~ 1 로의 거리값을 + 한 후 마이너스인지 확인 하는 코드

 

 

-간선 통제까지 해주었지만 제가 생각 했던 방법으로는 풀리지 않네요..

 

 

 

다시 시작하여 이번엔 다익스트라 알고리즘과 비슷하지만 음수 간선이 발생하였을때도 고려해주는 

 

벨만 포드 알고리즘을 이용해 봅시다. 

 

 

 

 

코드!

---

가장먼저 선언부

 

int T;
int N, M, W; // n개 지점 , m개 도로, w개 웜홀

// 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로   + 시간이 뒤로 감


//출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지? 출력

vector<pair<int, int>>city[501];  // 정방향

 

다음은 입력을 받아 줍시다.

cin >> T;
    while (T--) {

        cin >> N >> M >> W;

        for (int i = 1; i <= N; i++) {
            city[i].clear();
        }

        int tempStart, tempEnd, tempTime;

        for (int i = 1; i <= M; i++) { // 
            cin >> tempStart >> tempEnd >> tempTime;
            city[tempStart].push_back({ tempTime, tempEnd });
            city[tempEnd].push_back({ tempTime, tempStart });
        }

        for (int i = 1; i <= W; i++) {
            cin >> tempStart >> tempEnd >> tempTime;
            city[tempStart].push_back({ tempTime * (-1), tempEnd });
        }

 

여기까지는 다익스트라와 비슷했습니다.

 

 

 

다음은 벨만포드 알고리즘

 

[벨만포드] 알고리즘의 과정은 다음과 같습니다 .

1. 출발노드를 설정

2. 모든간선을 확인 , 최단거리 테이블을 갱신 >>> 이 과정을 N-1 (노드갯수-1) 번 반복

 

끝? 

 

여기서 한번더 간선을 확인하고 최단거리 테이블을 갱신할때,

테이블의 값이 음수가 나온다면?  >> 음수 사이클 발생!

 

 

그렇기에 아래처럼 간단하게 구현 가능합니다. 

bool bellman(int start) {
    vector<int> dist(N + 1, 987654321);
    bool updated = false;
    dist[start] = 0;
    //TC-1번 순회한다.
    for (int iter = 1; iter <= N; iter++) {
        updated = false;

        for (int here = 1; here <= N; here++)
            for (int i = 0; i < city[here].size(); i++) {
                int Tempind = city[here][i].second;
                int Tempdist = city[here][i].first;

                if (dist[Tempind] > dist[here] + Tempdist) {
                    dist[Tempind] = dist[here] + Tempdist;
                    updated = true;
                }
            }
    }
    return updated;
}

다익스트라 알고리즘과 비슷한 모양이네요

N번 반복하여 마지막에 음수사이클이 발생하는지 확인하는 방법!

 

 

위 처럼 할수도 있지만 좀 더 직관적으로 

 

bool bellman(int start) {
    vector<int> dist(N + 1, 987654321);
    bool updated = false;
    dist[start] = 0;
    //N-1번 순회한다.
    for (int iter = 0; iter < N-1; iter++) { 
        for (int here = 1; here <= N; here++) {
            for (int i = 0; i < city[here].size(); i++) {
                int Tempind = city[here][i].second;
                int Tempdist = city[here][i].first;

                if (dist[Tempind] > dist[here] + Tempdist) {
                    dist[Tempind] = dist[here] + Tempdist;
                    
                }
            }
        }
 
    } 

    updated = false;
    for (int here = 1; here <= N; here++) { // 마지막!
        for (int i = 0; i < city[here].size(); i++) {
            int Tempind = city[here][i].second;
            int Tempdist = city[here][i].first;

            if (dist[Tempind] > dist[here] + Tempdist) {
                dist[Tempind] = dist[here] + Tempdist;
                updated = true;
            }
        }
    }

    return updated;
}

이렇게 볼 수 있겠네요

 

끝!

 

 

이번 문제를 통해 배운 내용

1. 음수 사이클일땐 벨만포드 사용해보기

2. 문제 제대로 이해하기..

 

 

ALL

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


using namespace std;

int T;
int N, M, W; // n개 지점 , m개 도로, w개 웜홀

// 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로   + 시간이 뒤로 감


//출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지? 출력

vector<pair<int, int>>city[501];  // 정방향




bool bellman(int start) {
    vector<int> dist(N + 1, 987654321);
    bool updated = false;
    dist[start] = 0;
    //TC-1번 순회한다.
    for (int iter = 1; iter < N+1; iter++) {
        updated = false;

        for (int here = 1; here <= N; here++)
            for (int i = 0; i < city[here].size(); i++) {
                int Tempind = city[here][i].second;
                int Tempdist = city[here][i].first;

                if (dist[Tempind] > dist[here] + Tempdist) {
                    dist[Tempind] = dist[here] + Tempdist;
                    updated = true;
                }
            }
    }



    return updated;
}


int main() {
    
    cin >> T;
    while (T--) {

        cin >> N >> M >> W;

        for (int i = 1; i <= N; i++) {
            city[i].clear();
        }

        int tempStart, tempEnd, tempTime;

        for (int i = 1; i <= M; i++) { // 
            cin >> tempStart >> tempEnd >> tempTime;
            city[tempStart].push_back({ tempTime, tempEnd });
            city[tempEnd].push_back({ tempTime, tempStart });
        }

        for (int i = 1; i <= W; i++) {
            cin >> tempStart >> tempEnd >> tempTime;
            city[tempStart].push_back({ tempTime * (-1), tempEnd });
        }




        if (bellman(1))
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

 

 

 

 

틀린점이 있다면 댓 달아주세요!