[C++]백준 1261번 : 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

1. 접근

pq를 통한 bfs에서 각각의 방에 몇번 벽을 깨고 들어왔는지 3차원 배열에 저장을 하며 정답을 구했다.

해당 방식은 아래의 코드와 같고 정답을 받을 수 있었지만 시간과 메모리 사용량이 너무 크다고 생각했다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

struct state{
	int y, x, cnt;
};

struct comp{
	bool operator()(state a, state b){
		return a.cnt > b.cnt;
	}
};

int N, M, map[100][100];
string str;
bool chk[100][100][10000];
priority_queue<state, vector<state>, comp> pq;
pair<int, int> dir[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int ans = 0;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> N;
	for (int i = 0; i < N; i++){
		cin >> str;
		for (int j = 0; j < M; j++){
			map[i][j] = (int)(str.at(j)-'0');
		}
	}

	pq.push({ 0, 0, 0 });
	for (int i = 0; i <= N*N; i++)
		chk[0][0][i] = true;

	
	while (!pq.empty()){
		state tmp = pq.top();
		pq.pop();

		if (tmp.y == N - 1 && tmp.x == M - 1){
			ans = tmp.cnt;
			break;
		}

		for (int i = 0; i < 4; i++){
			int ny = tmp.y + dir[i].first, nx = tmp.x + dir[i].second;
			int nCnt = tmp.cnt;

			if (ny < 0 || ny >= N || nx < 0 || nx >= M)
				continue;

			if (map[ny][nx] == 1)
				nCnt++;

			if (!chk[ny][nx][nCnt]){
				chk[ny][nx][nCnt] = true;
				pq.push({ ny, nx, nCnt });
			}
		}
	}

	cout << ans;

	
	return 0;
}

 

2. 다른 방식

구하는 경로는 지나온 방의 개수가 아니라 최소로 벽을 부순 경로이다.

각 탐색 반복마다 하나의 방에 이미 더 적은 벽을 부수고 들어온 경우가 없다면 pq에 넣고

그렇지 않다면 pq에 넣지 않는 것에 착안하여 최소 비용으로 경로를 정하는 다익스트라 알고리즘을 적용했다.

 

2차원 배열로 map[y][x]에 몇번 방을 부수고 들어왔는지 chk[y][x]에 저장하고 이를 바탕으로 pq연산을 수행했다.

시간과 메모리를 확연하게 줄일 수 있었다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <climits>
#include <queue>

using namespace std;

struct state{
	int y, x, cnt;
};

struct comp{
	bool operator()(state a, state b){
		return a.cnt > b.cnt;
	}
};

int N, M, map[100][100];
string str;
int chk[100][100];
priority_queue<state, vector<state>, comp> pq;
pair<int, int> dir[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
int ans = 0;

int main(){

	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> M >> N;
	for (int i = 0; i < N; i++){
		cin >> str;
		for (int j = 0; j < M; j++){
			map[i][j] = (int)(str.at(j)-'0');
		}
	}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			chk[i][j] = INT_MAX;

	pq.push({ 0, 0, 0 });
	chk[0][0] = 0;
	
	while (!pq.empty()){
		state tmp = pq.top();
		pq.pop();

		if (chk[tmp.y][tmp.x] < tmp.cnt)
			continue;

		if (tmp.y == N - 1 && tmp.x == M - 1){
			ans = tmp.cnt;
			break;
		}

		for (int i = 0; i < 4; i++){
			int ny = tmp.y + dir[i].first, nx = tmp.x + dir[i].second;
			int nCnt = tmp.cnt;

			if (ny < 0 || ny >= N || nx < 0 || nx >= M)
				continue;

			if (map[ny][nx] == 1)
				nCnt++;

			if (chk[ny][nx] <= nCnt)
				continue;

			pq.push({ ny, nx, nCnt });
			chk[ny][nx] = nCnt;
		}
	}

	cout << ans;

	
	return 0;
}