백준 No.1261 [알고스팟]

BOJ No.1261 [알고스팟]

---

  문제 

1261번: 알고스팟 (acmicpc.net)

1261번: 알고스팟

---

  설명 

<알고리즘 분류>
 * Dijkstra (다익스트라)
 * 너비 우선 탐색 (BFS)

 

  주어진 미로의 각 좌표들을 노드라고 생각하고, 좌표에서 이동할 수 있는 방향은 상하좌우로 인접한 네 방향이므로 이 네 방향을 하나의 간선이라고 생각할 수 있다. 좌표의 최대 크기는 100 * 100 이다. 따라서 노드의 최대 개수는 10,000 개가 되며 한 노드당 좌표의 모서리에 위치한 자리들이 아닌 이상 4개의 간선을 가지므로 최대 총 40,000 개보다 적은 수의 간선을 갖게 된다. 따라서 좌표를 그래프화 시켜서 풀어도 메모리적으로 큰 비효율성은 없는 것 같다.

 

  5 * 5 맵에서 (2, 2) 좌표에 있는 노드에 대해 간선을 4 방향으로 추가하는 경우이다. 간선을 추가할 때 간선의 가중치의 값은 도착하는 노드의 좌표값으로 초기화를 해 준다. 그 간선을 통해 이동할 때 벽을 부수게 되는 경우인지 아닌지를 따져야 하기 때문이다.

 

  푼 사람마다 다르겠지만 나는 2차원 좌표를 하나의 1차원 배열로 치환하여 풀었다.

  칸마다 해당되는 좌표들은 모두 칸에 있는 숫자로 1차원 배열 치환을 한 것 이다. 그 후 다익스트라 알고리즘을 통해 0번째 노드에서 24번째 노드까지 가는 최소 비용 (최소 벽 부순 횟수) 를 구하면 된다. 

 

<정리>
1. 각 좌표들은 정점(노드), 어떠한 좌표와 상하좌우로 인접한 정점으로 이동하는 간선들을 이용하여 하나의 그래프를 만든다.
2. 이 그래프를 다익스트라 알고리즘을 통하여 목적지까지 가는 최소 벽 부수는 횟수를 알 수 있다.

---

  Code 

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

using namespace std;
typedef pair<int, int> pii;

struct ADJ {
	int node;
	int val;
};

struct comp {
	bool operator() (ADJ a, ADJ b) {
		if (a.val < b.val) return false;
		else if (a.val > b.val) return true;
		else if (a.node != b.node) return false;
	}
};

const int inf = 1000000;
vector<vector<int>> map;
vector<vector<ADJ>> adj;
vector<int> dist;
int w, h;

inline int Node(int r, int c) {
	return w * r + c;
}

void dijkstra(int start) {
	priority_queue<ADJ, vector<ADJ>, comp> pq;

	pq.push({ start, map[0][0] });

	while (!pq.empty()) {
		ADJ cur = pq.top(); pq.pop();

		if (cur.node == w * h - 1) break;
		if (cur.val > dist[cur.node]) continue;

		int size = adj[cur.node].size();

		for (int i = 0; i < size; i++) {
			ADJ next = adj[cur.node][i];

			if (dist[next.node] > cur.val + next.val) {
				dist[next.node] = cur.val + next.val;
				pq.push({ next.node, dist[next.node] });
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> w >> h;

	map.assign(h, vector<int>(w, 0));
	dist.assign(w * h, inf);
	adj.resize(w * h);

	string row;
	for (int i = 0; i < h; i++) {
		cin >> row;
		for (int j = 0; j < w; j++) {
			map[i][j] = row[j] - 48;

			if (i) {
				adj[Node(i, j)].push_back({ Node(i - 1, j), map[i - 1][j] });
				adj[Node(i - 1, j)].push_back({ Node(i, j), map[i][j] });
			}
			if (j) {
				adj[Node(i, j)].push_back({ Node(i, j - 1), map[i][j - 1] });
				adj[Node(i, j - 1)].push_back({ Node(i, j), map[i][j] });
			}
		}
	}

	dijkstra(0);

	if (dist[w * h - 1] != inf) cout << dist[w * h - 1];
	else cout << 0;
}