[백준 1261 - C++] 알고스팟

⬇️ 문제 출처

백준 1261 : 알고스팟

💡 접근 방법

deque, 0-1 BFS로 푸는 문제!

✏️ 풀이

벽을 부수지 않는 것을 push_front()로, 벽을 부수는 경우는 push_back()으로 deque에 넣어줬다. 그 후, (N, M)에 도착하면 최소의 벽을 부숴서 도착하는 경우이므로 출력한다!

⌨️ 소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
#include <queue>
#include <cstring>
#include <tuple>
#include <cmath>
#include <math.h>
#define MAX_N 1000+5
#define endl "\n"
const int INF = 987654321;
typedef long long ll;
using namespace std;
int map[500 + 5][500 + 5]; // 0 -> right down, 1 -> right up
int dy[] = { 0,1,0,-1 }, dx[] = { 1,0,-1,0 };
bool visited[500 + 5][500 + 5];
void solve() {
	int M, N;
	cin >> M >> N;
	for (int i = 1; i <= N; i++) {
		string s; cin >> s;
		for (int j = 0; j < s.length(); j++) {
			if (s[j] == '0') map[i][j + 1] = 0;
			else map[i][j + 1] = 1;
		}
	}

	deque<pair<pair<int, int>, int>> dq;
	dq.push_front({{ 1,1 }, 0});
	visited[1][1] = true;
	while (!dq.empty()) {
		int y = dq.front().first.first;
		int x = dq.front().first.second;
		int cnt = dq.front().second;
		dq.pop_front();
        
		if (y == N && x == M) {
			cout << cnt;
			return;
		}

		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 1 || ny > N || nx < 1 || nx > M) continue;
			if (visited[ny][nx]) continue;
			visited[ny][nx] = true;
			if (map[ny][nx]) {
				dq.push_back({ { ny,nx }, cnt + 1});
			}
			else {
				dq.push_front({ {ny,nx}, cnt });
			}
		}
	}
}

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	solve();
}

🔥🔥🔥