반응형
리뷰
경로 상에 신호등이 있어 기다렸다가 움직여야 하는 최단 경로 문제, 다른 문제와 다른점은 신호등의 방향이 정해져 있어 교차로에 진입하는 경우를 잘 분배해 주어야 했다.
https://www.acmicpc.net/problem/1400
문제 풀이
- 행 범위n, 열 범위 m, 시작 좌표 sx, sy 도착 좌표 ex, ey, 방향 배열, 맵 정보 lst배열을 전역 변수로 세팅한다.
- 우선 순위 큐에서 사용할 Pos구조체를 정의하고, compare함수도 넣어준다.
- 신호등 정보를 받을 구조체 Light를 정의하고, 신호등 배열 lights를 60크기로 설정해 준다.
- main함수에서 무한루프를 실행하고 input함수에서 n, m이 0, 0이라면 while루프를 종료해 준다.
- input함수를 통해 n, m값을 받고 만약 n과 m이 모두 0이라면 false를 반환해 준다.
- 입력 받은 값이 'A', 'B'라면 각각 시작 도착 좌표로 정의해주고, 0~9가 입력되면 cnt의 개수를 늘려준다.
- cnt의 개수만큼 신호등 정보를 입력받아 lights 배열에 신호등의 정보를 넣어준다.
- input함수의 리턴값이 true라면 다익스트라를 실행해 준다.
- Pos타입의 우선순위큐 pq를 초기화 하고, 2차원 거리 벡터 dist를 n * m사이즈로 내부값은 크게 설정한다.
- pq에 시작 좌표와 초기 거리 0을 넣어주고, 시작좌표의 거리 정보를 0으로 초기화 해준다.
- 다익스트라 탐색을 시작한다, 현재 위치로부터 4방향 탐색을 진행하고 범위 내면서 '.'가 아니라면 진행한다.
- 만약 현재 거리가 이동할 위치보다 크다면 탐색을 진행할 필요가 없이 continue 처리해 주면 된다.
- 이동할 위치가 맵상 0 ~ 9라면 신호등이므로 각 진입방향과 신호등 정보에 맞게 이동처리해 주어야 한다.
- 좌우로 이동하면서 신호등이 '-' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 좌우로 이동 가능한 시간대보다 작다면 이동이 가능하다.
- 좌우로 이동하면서 신호등이 '|' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 상하로 이동 가능한 시간대보다 크거나 같다면 이동이 가능하다.
- 상하로 이동하면서 신호등이 '-' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 좌우로 이동 가능한 시간대보다 크거나 같다면 이동이 가능하다.
- 상하로 이동하면서 신호등이 '|' 특성이라면 현재까지의 거리를 신호등 쿨타임으로 나눈 나머지 값이 상하로 이동 가능한 시간대보다 작다면 이동이 가능하다.
- 그 외의 경우에는 모두 이동 불가이므로 현재 위치에서 시간을 +1 하여 우선순위 큐에 다시 삽입해 준다.
- 만약 이동이 가능한 경우에는 모두 다음 위치로 이동시키고 dist정보를 최신화 해준다.
- 모든 최단 경로 탐색을 마친 뒤 도착지의 dist값이 초기값이라면 impossible을 출력, 아니라면 거리를 출력해 준다.
참고 사항
- 테스트케이스가 나누어져 있지만 입력을 받을때 기존의 자료구조를 덮어쓰는 형태이기 때문에 따로 초기화는 필요없다. (예를 들어, 이전 테케에서 신호등 9개를 썼더라도 다음 테케에서 신호등이 주어지지 않으면 사용할 일이 없다.)
- 신호등 배열의 크기를 60으로 설정한 이유는 0~9를 문자로 받아와 아스키코드를 활용하기 위함이다.
- 신호등의 쿨타임은 좌우 이동 가능한 시간대와 상하 이동 가능한 시간대를 합친 값이다.
- 이동 불가능한 케이스를 계산할때 현재 거리에 이동이 가능한 시간이 되도록 더해주는 방법이 더 최적화 일 것 같다.
- 하지만 코드 직관성을 위해 기존의 거리에서 + 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
반응형
'알고리즘 공부 > C++' 카테고리의 다른 글
[G2] 백준 16946번 벽 부수고 이동하기 4 C++ BFS, FloodFill, 너비 우선 탐색 (0) | 2024.09.17 |
---|---|
[G5] 백준 2166번 다각형의 면적 C++ 기하학, 신발끈 공식, 슈메르카우스키의 공식 (2) | 2024.09.16 |
[G4] 백준 7662번 이중 우선순위 큐 C++ 멀티셋, multiset (0) | 2024.09.16 |
[G3] 백준 2623번 음악프로그램 C++ 위상 정렬 (0) | 2024.09.15 |
[G2] 백준 7453번 합이 0인 네 정수 C++ 이분 탐색, 투 포인터, upper_bound, lower_bound, 정렬 (0) | 2024.09.15 |