[백준] 알고리즘 1261번 - 알고스팟문제

문제

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

1261번: 알고스팟

소스코드

#include <iostream>
#include <limits.h>
#include <vector>
#include <queue>
#include <algorithm>
#include<memory.h>
#include <stdio.h>
using namespace std;
int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
char arr[101][101];
int dist[101][101];
bool check[101][101];
deque<pair<int, int>> dq;

void bfs(int x, int y) {
	dq.push_back({ x,y });
	while (!dq.empty()) {
		int ox = dq.front().first;
		int oy = dq.front().second;
		dq.pop_front();
		for (int i = 0; i < 4; i++) {
			int nx = ox + dx[i];
			int ny = oy + dy[i];
			if (nx<1 || nx>n || ny<1 || ny>m) continue;
			if (arr[nx][ny]-'0' == 0 && !check[nx][ny]) {
				check[nx][ny] = true;
				dq.push_front({ nx,ny });
				dist[nx][ny] = dist[ox][oy];
			}
			if (arr[nx][ny]-'0' == 1 && !check[nx][ny]) {
				check[nx][ny] = true;
				dq.push_back({ nx,ny });
				dist[nx][ny] = dist[ox][oy] + 1;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> arr[i][j];
		}
	}
	bfs(1, 1);
	cout << dist[n][m];
}

해설

(1,1) -> (n,m) 으로가는 벽을 최소한으로 부셔서 갈 수 있는 횟수라고 합니다.

뭔가 냄새가 bfs냄새가 나는데, 문제를 읽어보면 상 하 좌 우 움직일 수 있고 최소횟수를 구하자고 했으니 우선 bfs로 해보자.

가중치를 생각해봐야하는데 우리가 구해야하는건 벽을 최소한으로 부수는 개수라고 해보자. 그렇다면 벽이 없이 그냥 이동할 수 있는 arr[x][y]=0일때는 벽을 부술 필요가 없으니 가중치는0이된다.

arr[x][y]=1일때는 벽을 부셔서 이동해야하니 가중치가1이된다.

그렇다면 가중치가 다르니 우선순위를 따져가면서 큐에 넣어야한다.

우리는 벽을 최대한 안부수면서 가는 것을 구해야하니 가중치가0인 순으로부터 먼저 덱의 앞부분에 넣어준다. 그다음 가중치가1은 덱의 뒷부분에 넣으면서 bfs를 진행하면된다.