[BOJ/C++] 1261(알고스팟)

Link

https://www.acmicpc.net/problem/1261

풀이 과정

1. 벽을 최소 몇 개 부수어야 하는가 -> BFS, DFS, Dijkstra
2. (1,1)에서 시작하여 (n,m)에서 끝나는 것으로 확정 -> Dijkstra

• 사실 다익스트라 외에도 BFS로 풀 수 있는 문제입니다. 다만 출제의도로 보거나 효율상으로 보거나 다익스트라가 더 좋을 것으로 보여 채택하였음

• N과 M으로 살짝 함정을 넣어놓은 문제입니다. 행과 열이 제대로 입력 및 탐색되고 있는지 주의할 것

• 다음 가는 경로에 벽이 있는지 유무는 사실 0과 1뿐인 board라 그냥 if문 없이 직접 대입을 통해 다음과 같이 식을 간소화하였습니다.
  if (dist[nx][ny] <= dist[x][y] + board[nx][ny]) continue;
  dist[nx][ny] = dist[x][y] + board[nx][ny];

정답 코드

1. Queue

#include<iostream>
#include<queue>
using namespace std;
#define p pair<int, int>
#define INF 987654321

int n, m;
int dist[101][101]{ 0 };
int board[101][101];
int dx[4]{ 0,1,0,-1 };
int dy[4]{ 1,0,-1,0 };

void dijkstra() {
	queue<p> q;
	q.push({ 1, 1 });
	dist[1][1] = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > m || ny < 1 || ny > n) continue;
			if (dist[nx][ny] <= dist[x][y] + board[nx][ny]) continue;
			dist[nx][ny] = dist[x][y] + board[nx][ny];
			q.push({ nx,ny });
		}
	}
}

void input() {
	cin >> n >> m;
	string s;
	for (int i = 1; i <= m; ++i) {
		cin >> s;
		for (int j = 1; j <= n; ++j) {
			board[i][j] = s[j - 1] - '0';
			dist[i][j] = INF;
		}
	}
}

void solution() {
	input();
	dijkstra();
	cout << dist[m][n];
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}

2. Priority_Queue

#include<iostream>
#include<queue>
using namespace std;
#define p pair<int, int>
#define INF 987654321

int n, m;
int dist[101][101]{ 0 };
int board[101][101];
int dx[4]{ 0,1,0,-1 };
int dy[4]{ 1,0,-1,0 };

void dijkstra() {
	priority_queue<p> q;
	q.push({ 1, 1 });
	dist[1][1] = 0;
	while (!q.empty()) {
		int x = q.top().first;
		int y = q.top().second;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || nx > m || ny < 1 || ny > n) continue;
			if (dist[nx][ny] <= dist[x][y] + board[nx][ny]) continue;
			dist[nx][ny] = dist[x][y] + board[nx][ny];
			q.push({ nx,ny });
		}
	}
}

void input() {
	cin >> n >> m;
	string s;
	for (int i = 1; i <= m; ++i) {
		cin >> s;
		for (int j = 1; j <= n; ++j) {
			board[i][j] = s[j - 1] - '0';
			dist[i][j] = INF;
		}
	}
}

void solution() {
	input();
	dijkstra();
	cout << dist[m][n];
}

int main() {
	cin.tie(0), cout.tie(0);
	ios_base::sync_with_stdio(0);
	solution();
	return 0;
}