BOJ - 1261번 알고스팟(c++)

문제 출처: https://www.acmicpc.net/problem/1261

사용한 언어

C++

문제 난이도

골드 4
(solved.ac를 이용한 난이도 체크)

문제 접근

사실 처음에 완전탐색으로 일일이 BFS 돌렸는데 시간초과 떴다. 그래서 벽 없는데로 최대한 갔다가 막힐때만 벽을 뚫으면 최소가 되지 않을까? 했다가 최소를 못구한다는 걸 알고 결국 다른 사람 풀이를 참고했다.

1. 최소로 벽 뚫기니깐 벽을 가중치라고 생각해보자
2. 최소의 가중치로 목적지까지 도착해야한다.
3. 최소 가중치를 구하는 알고리즘은 다양한데 그 중에 다익스트라를 사용한다.

다익스트라 관련 개념은 네트워크상에 많은 포스팅이 있기 때문에 생략한다.
나는 최소 비용 알고리즘들은 크루스칼(Union&Find), MST(우선순위큐), 다익스트라(배열) 이런식으로 이용한다. 다익스트라 자체를 노드 간선 문제에서만 사용한다고 생각했는데 이런 문제에서 적용될 수 있다는 걸 깨달았다.

통과 코드

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

using namespace std;

int N, M;
int board[101][101];
int dist[101][101];
int dy[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };

void bfs() {
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	dist[0][0] = 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 + dy[i][0];
			int ny = y + dy[i][1];
			if (nx <0 || ny<0 || nx>=M || ny>=N ) continue;
			if (board[nx][ny] == 1) {
				if (dist[nx][ny] > dist[x][y] + 1) {
					dist[nx][ny] = dist[x][y] + 1;
					q.push({ nx,ny });
				}
			}
			else if(board[nx][ny]==0) {
				if (dist[nx][ny] > dist[x][y]) {
					dist[nx][ny] = dist[x][y];
					q.push({ nx,ny });
				}
			}
		}
	}

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> M;
	string str;
	for (int i = 0; i < M; i++) {
		cin >> str;
		for (int j = 0; j < N; j++) {
			dist[i][j] = 987654321;
			board[i][j] = str[j] - '0';
		}
	}
	bfs();
	cout << dist[M - 1][N - 1] << "\n";
	return 0;
}

피드백

1. N,M을 통상적인 위치로 x,y로 썼다가 반대라는 걸 예제를 돌리다가 알았다. 문제를 자세하게 보자!
2. 백준 c++은 scanf("%1d", &board[i][j])로 해서 돌리면 틀렸습니다가 뜬다. 그러므로 입력은 string으로 받아야한다.