[백준 1261] 알고스팟

문제 요약

• N*M 사이즈의 배열에 알고스팟 운영진이 갇혀있습니다.
• 이 배열은 빈 칸이거나 벽으로 이루어져 있습니다.
• 알고스팟 운영진은 AOJ라는 무기를 갖고 있는데, 이 무기는 바로 옆에 있는 타깃 벽을 부수면서 해당 벽으로 이동하는 무기입니다.
• 벽을 가장 적게 쓰면서 (1,1)위치에서 (N,M) 위치에 도달하는 경우의 벽 부수는 횟수를 출력하세요.

입력

• 배열의 사이즈 M , N (1 ≤ N, M ≤ 100)
• 벽의 유무를 나타내는 2차원 배열

아이디어

벽을 1회 부수는 거를 비용으로 계산해서 다익스트라를 진행한다.

4 2
0001
1000
의 테스트 케이스의 경우엔 [0][2]위치로 가는 데의 비용은 0인 반면, [0][3]위치로 가는 데의 비용은 1이 든다.

삽질

문제 상에서 N*M의 순서가 입력에선 반대로 나와서 헷갈렸었다.
그에 따라 이름 바꾸기 refactor를 3번 연속 썼던..

BFS VS 다익스트라 고찰...

처음에는 BFS로 접근을 하려고 했다. BFS 역시 벽이 있는 상황에서 얼마나 짧은 거리로 도달할 수 있는가?(BFS의 LEVEL 문제)라는 문제를 풀 때 사용되기 때문이다.

하지만 BFS는 간선의 비용이 같은 상황에서만 쓰일 수 있다. BFS의 경우 레벨이 바뀔 때마다 항상 같은 비용(같은 레벨)의 방문 후보들을 큐에 저장한다.

다익스트라 알고리즘이 간선의 비용이 모두 같은 상황에서 동작한다면 BFS와 비슷하게 방문 하긴 할것이다.

다시 문제로 돌아와서, 이 경우는 벽이 없는 경우는 0원, 벽이 있는 경우는 1원이라는 비용 차이가 있으니... LEVEL로 접근할 순 없었다. 새로운 노드를 PQ에 넣을 때 부모 노드와 같은 비용이 든다는 데서 일반적인 다익스트라가 아니라서 거부감이 생겼지만... 뭐 무료로 한걸음 순간이동 해주는 착한 사람이 나타났다는 상상을 하면서 나 자신을 납득시켰다.

소스코드

#include<iostream>
#include<string>
#include<memory.h>
#include<queue>
using namespace std;
struct candi {
	int i, j, c;
};
struct comp {
	bool operator()(candi& a, candi& b) {
		return a.c > b.c;
	}
};
int INF = 100 * 100;
int n, m;
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
int inbox(int i, int j) {
	return i >= 0 && i < n&& j >= 0 && j < m;
}

int main() {
	bool tab[100][100];
	string in;
	cin >> m >> n;

	for (int i = 0; i < n; i++) {
		cin >> in;
		for (int j = 0; j < m; j++) {
			tab[i][j] = (in[j] == '1'? true:false );
		}
	}
	int costs[100][100];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			costs[i][j] = INF;
		}
	}

	priority_queue<candi,vector<candi>, comp> q;
	q.push(candi{ 0,0,0 });

	while (!q.empty()) {
		candi cur = q.top();
		q.pop();
		if (cur.c >= costs[cur.i][cur.j]) {
			continue;
		}

		costs[cur.i][cur.j] = cur.c;
		for (int k = 0; k < 4; k++) {
			if (inbox(cur.i + di[k], cur.j + dj[k])) {
				candi child = candi{ cur.i + di[k], cur.j + dj[k] ,cur.c};
				if (tab[child.i][child.j]) child.c++;//벽이 있다면 벽 부수는 비용 추가

				if (child.c < costs[child.i][child.j]) {
					q.push(child);
				}
			}
		}
	}
	cout << costs[n - 1][m - 1];

}