[G1] 백준 24042번 횡단보도 C++ 최단 경로, 다익스트라, dijkstra

리뷰

 

정수형 변수 타입을 잘 확인하자.. 처음에 틀리고 나서 모두 long long으로 바꿔줬으나 다익스트라 리턴 형식을 int로 두었었다.

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

 

문제 풀이

1. n, m을 지역변수로 설정한다, long long타입 거리 배열을 10만 1 크기로 초기화 해준다.
2. 시뮬레이션 상에서 현재 위치 정보가 될 Pos구조체를 정의해 준다. pq를 활용할 것이니 내부에 compare 함수 포함
3. 인접 리스트를 표시할 EDGE 구조체를 정의해 준다, 노드와 해당 노드의 신호등 인덱스 정보가 담긴다.
4. EDGE타입의 2차 배열 path를 초기화 해준다. 해당 벡터를 통해 인접리스트를 체크할 것이다.
5. n과 m을 입력 받고 path의 사이즈를 n + 1로 초기화 해준 뒤 거리 배열의 1 ~ n인덱스를 굉장히 큰 값으로 초기화 해준다.
6. m개의 간선 정보를 입력받고 두 노드 a, b에 대해 양방향 간선을 추가해 준다, 이때 i를 인덱스로 같이 넘겨준다.
7. 다익스트라를 진행해 준다, 문제의 요구사항은 1에서 n까지의 최소 거리를 구하는 것이니 1부터 시작해 준다.
8. 핵심은 신호등을 갈 수 있냐 없냐이며, 갈 수 없을 경우 얼마나 많은 거리를 추가해 주어야 하냐이다.
9. 현재 시간을 m값으로 나눈 나머지 값(이하 md)이 이동할 노드의 index와 같다면 신호등을 통해 이동할 수 있는 경우이다.
10. 만약 이동할 수 없다면 신호등에 불이 들어올때 까지 대기를 해줘야 한다. 이때도 두가지 케이스로 나누어 진다.
11. 다음 노드의 index가 md보다 크다면 사이클이 필요 없다, 현재 시간에 다음 노드의 index - md만큼 더해준다.
12. 만약 md가 더 크다면 사이클을 한바퀴 돌려주어야 한다. 현재 시간에 m - md + 다음 노드의 index만큼 더해준다.
13. 신호등을 건너는 시간은 1분이 소요되기에 위에서 구한 값에 +1을 해주어야 한다.
14. 해당 값이 다음 노드로 가는 거리보다 작을 경우 갱신해 주고 우선순위 큐에 추가해 준다.
15. 모든 루프가 종료된 후 dist[n]을 출력해 주면 된다.

 

참고 사항

거리 관련한 변수 및 함수의 정수형 타입을 long long으로 빠짐없이 바꿔 주어야 한다.

신호등 관련 로직은 직접 손으로 그려보면 좀 더 빠르게 이해가 가능하다.

문제 제약 사항에 모든 지역은 횡단보도를 통해 서로 직, 간접적으로 연결되어 있다. 라고 적혀있기에 갈 수 없는 경우는 없다.

 

정답 코드

#include<iostream>
#include<queue>
#define ll long long

using namespace std;

int n, m;
ll dist[100001];

struct Pos { // 다익스트라용 구조체
	ll t; // 시간
	int node; // 현재 노드
	bool operator<(const Pos& other) const { // 시간 순으로 compare
		return t > other.t;
	}
};

struct EDGE { // 인접 리스트용 구조체
	int next, idx; // 다음 노드, 초록불이 열리는 인덱스
};

vector<vector<EDGE>> path; // 인접 리스트

long long dijkstra() {
	priority_queue<Pos> pq;
	pq.push({ 0, 1 }); // 1부터 시작
	dist[1] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		ll ct = pos.t; // 현재 시간
		int cn = pos.node; // 현재 노드

		if (ct != dist[cn]) continue; // 이미 더 빠른 값이 들와 있는 경우

		for (EDGE edge : path[cn]) { // 인접 리스트 탐색
			// green = 해당 노드의 신호등이 켜지는 인덱스, nn = 해당 노드, md = 현재 시간을 m값으로 나눈 값 (인덱스 비교용)
			int green = edge.idx, nn = edge.next, md = ct % m; 
			ll nt = ct; // 우선 현재시간과 동일하게 적용
			if (md != green) { // 신호등에 불이 켜져있는지 체크
				if (md < green) nt += green - md; // 한바퀴 돌 필요가 없는경우
				else nt += m - md + green; // 한바퀴 돌아야 하는 경우
			}
			if (dist[nn] > nt + 1) { // 최대값 계산
				dist[nn] = nt + 1;
				pq.push({ nt + 1, nn });
			}
		}
	}
	return dist[n]; // n번째 노드까지의 최소 거리 출력
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	path.resize(n + 1);
	for (int i = 1; i <= n; i++) dist[i] = 1e18; // 최대한 큰값으로 설정
	for (int i = 0; i < m; i++) { // 양방향 간선 추가
		int a, b; cin >> a >> b;
		path[a].push_back({ b, i });
		path[b].push_back({ a, i });
	}
	cout << dijkstra();
}