백준 1261번 알고스팟(C++)

벽을 부수고 이동한다는게 무슨 말인지 모를 수 있지만 결국 비용이 1인길을 선택하느냐 0인길을 선택하느냐의 차이이다. 

우리는 목적지까지 최소한으로 이동해야하기 때문에 최대한 0인부분을 잘 이용해야한다. 그렇기 때문에 이 문제는 0-1 BFS 최소비용 or 다익스트라 문제이다.

 

처음에는 아래 코드로 했다가 예제에서 틀렸다.

#include<iostream>
#include<algorithm>
#include<deque>

#define MAX 1001
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

deque<pair<int, int>> Q;
int dis[MAX][MAX];
int wall[MAX][MAX];
bool visited[MAX][MAX] = { false, };
void BFS(int N, int M,char boad[MAX][MAX]) {
	Q.push_front(make_pair(0, 0));

	while (!Q.empty()) {
		int RowX = Q.front().first;
		int ColY = Q.front().second;

		Q.pop_front();

		if(visited[RowX][ColY] == true){
			continue;
		}

		if (RowX == N - 1 && ColY == M - 1) {
			cout << wall[RowX][ColY];
		}

		visited[RowX][ColY] = true;

		for (int i = 0; i < 4; i++) {
			int nRow = RowX + dx[i];
			int nCol = ColY + dy[i];
			if (nRow > -1 && nRow < N && nCol > -1 && nCol < M) {
				if (boad[nRow][nCol] == '0') {
					Q.push_front(make_pair(nRow, nCol));
					wall[nRow][nCol] = wall[RowX][ColY];

				}
				else {
					Q.push_back(make_pair(nRow, nCol));
					wall[nRow][nCol] = wall[RowX][ColY] + 1;
				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	char boad[MAX][MAX];
	int N, M;

	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		string str; cin >> str;
		for (int j = 0; j < M; j++) {
			boad[i][j] = str[j];
			wall[i][j] = 0;
		}
	}
	BFS(N, M, boad);
}

 위 코드가 틀린 이유는 방문 표시를 while이 한 번 돌았을 때 마다 체크를 했기 때문이다. 반복문에서 큐에 삽입하면서 이미 벽의 정보에 대한 작업을 완료했는데 이러면 같은 작업을 몇번씩 하는 것과 똑같다.

 

 

정답코드

#include<iostream>
#include<deque>

#define MAX 101
using namespace std;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };

deque<pair<int, int>> Q;
int dis[MAX][MAX];
int wall[MAX][MAX];
bool visited[MAX][MAX] = { false, };
void BFS(int N, int M,char boad[MAX][MAX]) {
	Q.push_front(make_pair(0, 0));

	while (!Q.empty()) {
		int RowX = Q.front().first;
		int ColY = Q.front().second;

		Q.pop_front();

		if (RowX == N - 1 && ColY == M - 1) {
			cout << wall[RowX][ColY];
		}

		for (int i = 0; i < 4; i++) {
			int nRow = RowX + dx[i];
			int nCol = ColY + dy[i];
			if (nRow > -1 && nRow < N && nCol > -1 && nCol < M && visited[nRow][nCol] == false) {
				if (boad[nRow][nCol] == '0') {
					Q.push_front(make_pair(nRow, nCol));
					wall[nRow][nCol] = wall[RowX][ColY];
					visited[nRow][nCol] = true;
				}
				else {
					Q.push_back(make_pair(nRow, nCol));
					wall[nRow][nCol] = wall[RowX][ColY] + 1;
					visited[nRow][nCol] = true;

				}
			}
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	char boad[MAX][MAX];
	int N, M;

	cin >> M >> N;

	for (int i = 0; i < N; i++) {
		string str; cin >> str;
		for (int j = 0; j < M; j++) {
			boad[i][j] = str[j];
			wall[i][j] = 0;
		}
	}
	BFS(N, M, boad);
}

짜릿한 0ms