BOJ 1261 - 알고스팟

• N X M(1<=N,M<=100) 크기의 미로에서 (1, 1)에서 (N, M)으로 갈 때 부숴야 하는 최소한의 벽의 개수를 구하는 문제이다.(1인 칸이 벽으로 채워졌다고 생각하면 된다. 처음 들어갈 때만 벽을 부수는 느낌)

문제 풀이

• 벽을 가중치라 정하고 Dijkstra’s를 돌리면 된다.

소스코드

//Brute-force
#include<bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int n, m;
bool mz[100][100], t[100][100];
int v[100][100];
void f(int ci, int cj, int w){
	if(mz[ci][cj]) w++;
	if(v[ci][cj]<=w) return;
	v[ci][cj]=w;
	if(ci==n && cj==m) return;
	if(ci>0) f(ci-1, cj, w);
	if(cj<m-1) f(ci, cj+1, w);
	if(ci<n-1) f(ci+1, cj, w);
	if(cj>0) f(ci, cj-1, w);
}

int main()
{
	string s;
	cin>>m>>n;
	for(int i=0;i<n;i++){
		getline(cin, s, '\n');
		while(s=="") getline(cin, s, '\n');
		for(int j=0;j<m;j++) mz[i][j]=s[j]-48;
	}
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) v[i][j]=10000;
	f(0, 0, 0);
	cout<<v[n-1][m-1];
}

//Dijkstra's
#include<bits/stdc++.h>
#define F first
#define S second
using namespace std;
typedef pair<int, pair<int, int> > ppii;

int n, m;
int ww[100][100], di[4]={-1, 1, 0, 0}, dj[4]={0, 0, -1, 1};
bool mz[100][100];

int main()
{
	cin>>m>>n;
	for(int i=0;i<n;i++){
		char s[101];
		cin>>s;
		for(int j=0;j<m;j++) mz[i][j]=s[j]-48;
	}
	for(int i=0;i<n;i++) for(int j=0;j<m;j++) ww[i][j]=-10000;
	priority_queue<ppii, vector<ppii>> pq;
	ww[0][0]=0;
	pq.push({0, {0, 0}});
	while(!pq.empty()){
		int cw=pq.top().F, ci=pq.top().S.F, cj=pq.top().S.S;
		pq.pop();
		if(ww[ci][cj]>cw) continue;
		for(int i=0;i<4;i++){
			int ni=ci+di[i], nj=cj+dj[i], nw=cw-mz[ni][nj];
			if(ni>-1 && nj>-1 && ni<n && nj<m && ww[ni][nj]<nw){
				pq.push({nw, {ni, nj}});
				ww[ni][nj]=nw;
			}
		}
	}
	cout<<-ww[n-1][m-1];
}

풀고나서

• Brute-force를 연습하기 위해 풀었다가(500ms) 다른 사람들이 너무 빨리 풀어서 어떻게 풀었는지 보았다. 벽을 한 번 부수고 이동했다가 다시 부순 방으로 돌아올 일이 없기 때문에 다익스트라 알고리즘을 적용할 수 있다.

• ws가 c++ keyword인 것을 알게되었다.

• 다익스트라, priority_queue를 써도 메모리를 50% 덜쓰는 코드들이 있는데 봐도 무슨 차인지 모르겠다.