포스팅 목적
최단거리 문제를 풀면서 자주 해왔던 실수가 이 문제에서 종합적으로 발생해서 정리해두고자 함이다. 컴파일 할 때 오류가 발생되지 않아서 디버깅이 막막한 런타임 오류들이다.
매번 그래프를 인접 행렬로 저장하고 문제를 풀었다. 2차원 격자 문제에 대해서는 다익스트라 알고리즘을 적용하지 못하고 BFS만 활용했는데, 이 문제가 격자를 다익스트라로 푸는 좋은 예제다.
아래 풀이는 사실 다익스트라의 relaxation을 활용했다고 보기는 힘든데, 다른 풀이들을 보면 조건에 맞게 가중치를 직접 부여해서 좀 더 다익스트라 알고리즘에 가깝게 풀이한 것들이 있다.
실수 목록
아래 코드에 어떤 부분인지 표시해놨음.
1. 변수 n, m
가장 많이 하는 실수다. 주로 정점과 간선의 수를 가지는 변수 n과 m을 가장 먼저 할당해준다. 선언만 하고 할당을 안 해주는 실수도 한다. 이번에는 n과 m이 같다고 생각하는 실수를 저질렀다.
2. for문 제어 변수
for문 속에 for문이 있을 때, 제어 변수를 다르게 선언한다. 서로 붙어 있을 경우가 대부분인데, 아래 코드처럼 떨어져 있을 때, 제어 변수가 다르게 선언되는 것을 자주 잊게된다. 변수 i가 습관이라 그런 것 같다.
3. 우선순위 큐 pop()
while문의 조건이 !pq.empty() 이므로 반드시 pop()을 해줘야 된다. 무한루프로 빠지기 때문에 상대적으로 찾기 쉬운 실수긴 하다. pop()과 동시에 값이 할당되면 좋으련만.. 큐나 스택에 저장된 값을 사용할 때, pop()해주는 걸 잊지말자.
4. 등호 ==
이건 실수를 잘 안 하는데, 이번에 저지르고 보니까 되게 찾기 힘들다는 것을 알았다. 내가 처음부터 직접 짠 코드가 아니면 옮기는 과정에서 주로 이런 실수를 하는 것 같다. 코드 참고할 때 주의하자.
코드
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF 50
#define MAX 51
int res1, res2;
int s_row, s_col, e_row, e_col;
char map[MAX][MAX];
int dist[MAX][MAX];
int drow[] = {-1, 0, 1, 0};
int dcol[] = {0, 1, 0, -1};
class Info {
public:
int row, col, step, side;
bool operator<(const Info &rhs) const {
if (this->step == rhs.step) return this->side > rhs.side;
return this->step > rhs.step;
}
};
priority_queue<Info> pq;
int main()
{
ios_base::sync_with_stdio(false);
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) { <------------------- n과 m
cin >> map[i][j];
if (map[i][j] == 'S') {
s_row = i;
s_col = j;
} else if (map[i][j] == 'F') { <------------------ =, ==
e_row = i;
e_col = j;
}
dist[i][j] = INF;
}
}
pq.push({s_row, s_col, 0, 0});
dist[s_row][s_col] = 0;
while (!pq.empty()) {
auto cur = pq.top(); pq.pop(); <------------------ pop() 해주기
int row = cur.row;
int col = cur.col;
int step = cur.step;
int side = cur.side;
bool end = false;
for (int i = 0; i < 4; ++i) {
int nrow = row + drow[i];
int ncol = col + dcol[i];
if (nrow == e_row && ncol == e_col) {
end = true;
res1 = step;
res2 = side;
break;
}
if (nrow < 1 || nrow > n || ncol < 1 || ncol > m) continue; <------------------- n과 m
if (dist[nrow][ncol] != INF) continue;
if (map[nrow][ncol] == 'g') {
pq.push({nrow, ncol, step + 1, side});
}
else if (map[nrow][ncol] == '.') {
bool flag = false;
for (int j = 0; j < 4; ++j) {
if (map[nrow + drow[j]][ncol + dcol[j]] == 'g') { <------ for 문 속의 for문에서 변수 구분
flag = true;
pq.push({nrow, ncol, step, side + 1});
}
}
if (!flag) pq.push({nrow, ncol, step, side});
}
dist[nrow][ncol] = dist[row][col] + 1;
}
if (end) break;
}
cout << res1 << ' ' << res2 << endl;
return 0;
}