맞추는데 이틀이나 걸린 문제.
처음에는 weight로 막혔을 때만 1씩 더해주면 되겠네~ 하면서 풀었는데 메모리 초과가 났다.
메모리 초과는 또 뭔가 싶어 찾아보니 주로 같은 값이 중복되어 저장될 때 발생한다고 한다.
그래서 하나씩 손버깅 해보았더니 상하좌우 움직이느라 중복된 값이 큐에 들어가서 큐가 터지는 것 같았다.
문제의 해결은 의외의 곳에서 찾았다. 바로 이 부분 때문에 메모리 초과가 발생했던 것이다.
if(MAP[nr][nc] == '0') {
dist[nr][nc] = MIN(dist[nr][nc], dist[r][c]);
}
else { // MAP[nr][nc] == '1'
dist[nr][nc] = MIN(dist[nr][nc], dist[r][c] + 1);
}
q.push(make_pair(nr, nc));
이 부분은 현재 dist[nr][nc]의 값과 dist[r][c](+1)의 값 중 작은 값을 dist[nr][nc]의 값으로 저장하기 위해 작성한 코드이다.
예를 들어 다음과 같은 MAP이 있고, 위-오른쪽-아래-왼쪽의 순서로 옆 방을 탐색한다고 하자.
source의 dist값을 0으로 변경하고, source의 오른쪽 옆 방과 아랫방을 순서대로 본다.
먼저 source의 오른쪽 옆 방을 본다. 벽을 하나 뚫어야 하기 때문에 dist가 1이 되고, 큐에 오른쪽 방을 집어넣는다.
다음에는 source의 아랫방을 본다. 벽이 없기 때문에 dist는 source의 dist와 같은 0이다. 마찬가지로 큐에 아랫방을 넣어준다.
source를 봤으므로, 큐에서 다음 값을 꺼낸다. 시곗방향으로 이동했기 때문에 현재 방은 MAP[1][2](오른쪽 방)이다.
이때 [1][1]에서 [2][2]로 이동하려면 벽을 뚫지 않아도 되기 때문에 여전히 dist의 값은 1이다. 따라서 현재까지 목적지에 도달하기 위해 뚫어야 하는 벽의 개수는 1이다.
이제 큐에서 또 다음 값을 꺼내자.
이 경우 목적지까지 이동하는데 벽을 하나도 부수지 않는다. 즉, 이미 목적지의 dist값이 1이지만, 탐색을 계속하면서 더 작은 값이 올 수도 있기 때문에 현재의 값과 새로 들어오는 값 중 min값을 dist값으로 저장하면 된다.
이 방식은 답을 구해주나, 큐에 같은 값이 계속 들어오는 문제가 발생한다. 위의 예시에서 [1][2]에서도 [2][2]를 큐에 집어넣고, [2][1]에서도 [2][2]를 큐에 집어넣어 큐 안에 [2][2]가 중복되어 들어있게 된다. 만약 방의 사이즈가 100x100이라면 메모리가 터질 것이다.
이러한 문제를 해결하기 위해서는 dist의 값이 갱신되는 경우에만 큐에 push해주면 된다.
dist[nr][nc] = MIN(dist[nr][nc], dist[r][c]);
...
q.push(make_pair(nr, nc));
이라고 작성해버리면 dist의 값이 갱신되지 않아도 큐에 집어넣게 되어 중복이 발생한다. 대신
if (dist[nr][nc] > dist[r][c]) {
dist[nr][nc] = dist[r][c];
q.push(make_pair(nr, nc));
}
와 같이 값의 변경이 있는 경우에만 push에 최대한 큐에 덜 쌓이도록 하자는 것이다.
그런데 메모리 초과는 해결했으나 여전히 틀렸습니다가 떴다. 그래서 문제를 뭔가 잘못 풀고 있다는 걸 깨닫고 다 지우고 다익스트라로 다시 풀었다. 큐 대신 <weight, <row, col» 타입의 PQ를 사용해 구현했다.
벽의 유무를 weight로 나타내 벽이 없는 쪽부터 먼저 탐색하도록 해주었더니 올바른 코드를 작성할 수 있었다!
휴… 이게 왜 이틀이나 걸렸을까 ㅠㅠ
그리고 또 memset이 안되서 엄청 멘붕했었다. dist 배열 초기화할 때 자신있게 memset(dist, INF, sizeof(dist));라 작성했는데 디버깅할 때 보니 이상한 값이 마구 찍혀있었다 😱 그래서 폭풍서치했고 그 결과
memset으로 1바이트가 아닌 변수를 초기화할 때는 0 이외의 값을 사용하면 안 된다는 것을 알게되었다.
memset(void * ptr, int value, size_t num)은 ptr에 의해 allocate된 memory block의 num 바이트 만큼을 value로 채우는 함수라고. 이때 각 byte 를 채우기 때문에 memset(dist, 4, sizeof(dist))으로 실행했을 때 dist[1][1]의 값이 00000000 00000000 00000000 00000100이 아니라 00000100 00000100 00000100 00000100이 저장되었던 것이다.
1 바이트 단위가 아닌 자료형을 0이 아닌 값으로 초기화할 때는 fill_n()등을 사용하자.
#include <iostream>
#include <string>
#include <utility> // pair
#include <queue> // pq
#define MAX 101
#define INF 987654321
using namespace std;
int M, N;
int dr[4] = { -1, 1, 0, 0 }; // UP DOWN LEFT RIGHT
int dc[4] = { 0, 0, -1, 1 };
char MAP[MAX][MAX];
int dist[MAX][MAX];
bool inMap(int r, int c) {
if (1 <= r && r <= N && 1 <= c && c <= M) return true;
else return false;
}
void dijkstra(int row, int col) {
priority_queue< pair<int, pair<int, int> > > pq; // (weight, (row, col))
dist[row][col] = 0;
pq.push({ 0, {1, 1} });
while (!pq.empty()) {
int w = pq.top().first; // 벽의 유무 (0/1)
int r = pq.top().second.first;
int c = pq.top().second.second;
pq.pop();
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (inMap(nr, nc)) {
if (dist[nr][nc] > dist[r][c] + w) {
dist[nr][nc] = dist[r][c] + w;
pq.push(make_pair(MAP[nr][nc]-'0', make_pair(nr, nc)));
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i, j;
string str;
cin >> M >> N;
for (i = 1; i <= N; i++) {
cin >> str;
for (j = 0; j < M; j++) {
MAP[i][j + 1] = str[j];
dist[i][j + 1] = INF;
}
}
dijkstra(1, 1);
cout << dist[N][M] << endl;
return 0;
}