알고리즘 공부/C++

[G2] 백준 1400번 화물차 C++ 다익스트라, 최단 경로, 구현

마달랭 2024. 9. 16. 15:28
반응형

리뷰

경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.

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

 

문제 풀이

  1. 행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.
  2. 우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.
  3. 신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.
  4. main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.
  5. input함수를 통해 n, m값을 받고 만약 n과 m이 모두 0이라면 false를 반환해 준다.
  6. 입력 받은 값이 'A', 'B'라면 각각 시작 도착 좌표로 정의해주고, 0~9가 입력되면 cnt의 개수를 늘려준다.
  7. cnt의 개수만큼 신호등 정보를 입력받아 lights 배열에 신호등의 정보를 넣어준다.
  8. input함수의 리턴값이 true라면 다익스트라를 실행해 준다.
  9. Pos타입의 우선순위큐 pq를 초기화 하고, 2차원 거리 벡터 dist를 n * m사이즈로 내부값은 크게 설정한다.
  10. pq에 시작 좌표와 초기 거리 0을 넣어주고, 시작좌표의 거리 정보를 0으로 초기화 해준다.
  11. 다익스트라 탐색을 시작한다, 현재 위치로부터 4방향 탐색을 진행하고 범위 내면서 '.'가 아니라면 진행한다.
  12. 만약 현재 거리가 이동할 위치보다 크다면 탐색을 진행할 필요가 없이 continue 처리해 주면 된다.
  13. 이동할 위치가 맵상 0 ~ 9라면 신호등이므로 각 진입방향과 신호등 정보에 맞게 이동처리해 주어야 한다.
  14. 좌우로 이동하면서 신호등이 '-' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 좌우로 이동 가능한 시간대보다 작다면 이동이 가능하다.
  15. 좌우로 이동하면서 신호등이 '|' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 상하로 이동 가능한 시간대보다 크거나 같다면 이동이 가능하다.
  16. 상하로 이동하면서 신호등이 '-' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 좌우로 이동 가능한 시간대보다 크거나 같다면 이동이 가능하다.
  17. 상하로 이동하면서 신호등이 '|' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 상하로 이동 가능한 시간대보다 작다면 이동이 가능하다.
  18. 그 외의 경우에는 모두 이동 불가이므로 현재 위치에서 시간을 +1 하여 우선순위 큐에 다시 삽입해 준다.
  19. 만약 이동이 가능한 경우에는 모두 다음 위치로 이동시키고 dist정보를 최신화 해준다.
  20. 모든 최단 경로 탐색을 마친 뒤 도착지의 dist값이 초기값이라면 impossible을 출력, 아니라면 거리를 출력해 준다.

 

 

참고 사항

  1. 테스트케이스가 나누어져 있지만 입력을 받을때 기존의 자료구조를 덮어쓰는 형태이기 때문에 따로 초기화는 필요없다. (예를 들어, 이전 테케에서 신호등 9개를 썼더라도 다음 테케에서 신호등이 주어지지 않으면 사용할 일이 없다.)
  2. 신호등 배열의 크기를 60으로 설정한 이유는 0~9를 문자로 받아와 아스키코드를 활용하기 위함이다.
  3. 신호등의 쿨타임은 좌우 이동 가능한 시간대와 상하 이동 가능한 시간대를 합친 값이다.
  4. 이동 불가능한 케이스를 계산할때 현재 거리에 이동이 가능한 시간이 되도록 더해주는 방법이 더 최적화 일 것 같다.
  5. 하지만 코드 직관성을 위해 기존의 거리에서 + 1을 한 경우로 로직을 짰다, 다만 이 경우에는 기존의 다익스트라 방법과 같이 if (dist[cx][cy] != cd) 와 같은 로직을 넣어주면 안된다. (사실 시간 차이가 거의 없다.)

 

 

정답 코드

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

using namespace std;

int n, m, sx, sy, ex, ey;
int dx[] = { 1 ,-1 ,0 ,0 };
int dy[] = { 0, 0, 1, -1 };
string lst[20];

struct Pos {
	int x, y, d;
	bool operator<(const Pos& other) const {
		return d > other.d;
	}
};

struct Light {
	int dir, ew, sn, ct;
};

Light lights[60];

bool input() {
	cin >> n >> m;
	if (!n && !m) return false;
	int cnt = 0;
	for (int i = 0; i < n; i++) {
		cin >> lst[i];
		for (int j = 0; j < m; j++) {
			if (lst[i][j] == '.' || lst[i][j] == '#') continue;
			else if (lst[i][j] == 'A') sx = i, sy = j;
			else if (lst[i][j] == 'B') ex = i, ey = j;
			else cnt++;
		}
	}
	while (cnt--) {
		char idx, dir;
		int ew, sn;
		cin >> idx >> dir >> ew >> sn;
		lights[idx].dir = dir, lights[idx].ew = ew, lights[idx].sn = sn, lights[idx].ct = ew + sn;
	}
	return true;
}

void dijkstra() {
	priority_queue<Pos> pq;
	vector<vector<int>> dist(n, vector<int>(m, 1e9));
	pq.push({ sx, sy, 0 });
	dist[sx][sy] = 0;

	while (!pq.empty()) {
		Pos pos = pq.top(); pq.pop();
		int cx = pos.x, cy = pos.y, cd = pos.d;
		
		for (int i = 0; i < 4; i++) {
			int nx = cx + dx[i], ny = cy + dy[i], nd = cd + 1;
			if (0 <= nx && nx < n && 0 <= ny && ny < m && lst[nx][ny] != '.') {
				if (dist[nx][ny] <= nd) continue;
				if ('0' <= lst[nx][ny] && lst[nx][ny] <= '9') {
					Light light = lights[lst[nx][ny]];
					char dir = light.dir; int ew = light.ew, sn = light.sn, ct = light.ct;
					if (i > 1 && dir == '-' && cd % ct < ew);
					else if (i > 1 && dir == '|' && cd % ct >= sn);
					else if (i <= 1 && dir == '-' && cd % ct >= ew);
					else if (i <= 1 && dir == '|' && cd % ct < sn);
					else {
						pq.push({ cx, cy, nd });
						continue;
					}
				}
				dist[nx][ny] = nd;
				pq.push({ nx, ny, nd });
			}
		}
	}
	if (dist[ex][ey] == 1e9) cout << "impossible\n";
	else cout << dist[ex][ey] << "\n";
}

int main() {
	while (1) {
		if (!input()) break;
		dijkstra();
	}
}

 

 

728x90
반응형