[BOJ] 1261 : 알고스팟 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. BFS 탐색을 진행한다.

2. visit 배열을 dp배열로 선언한다.

dp[x][y] : (0, 0)에서 (x, y) 지점까지 오는데 필요한 벽을 부수는 최소 횟수.

현재 지점에서 다음 지점으로 넘어갈 때, 벽이라면 현재 dp 값 + 1 보다 크면 탐색을 진행하고,

벽이 아니라면 현재 dp값 보다 크면 탐색을 진행한다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m, dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 }, dp[100][100] = {};
	char map[100][101] = {};

	cin >> m >> n;
	for (int i = 0; i < n; i++)
		cin >> map[i];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			dp[i][j] = 99999999;

	queue<pair<int, int>> q;
	q.push(make_pair(0, 0));
	dp[0][0] = 0;

	while (!q.empty()) {
		pair<int, int> s = q.front();
		q.pop();

		int curX = s.first, curY = s.second;
		for (int i = 0; i < 4; i++) {
			int nextX = curX + dx[i], nextY = curY + dy[i];
			if (0 <= nextX && nextX < n && 0 <= nextY && nextY < m) {
				if (dp[curX][curY] + 1 < dp[nextX][nextY] && map[nextX][nextY] == '1') {
					dp[nextX][nextY] = dp[curX][curY] + 1;
					q.push(make_pair(nextX, nextY));
				}
				else if(dp[curX][curY] < dp[nextX][nextY] && map[nextX][nextY] == '0'){
					dp[nextX][nextY] = dp[curX][curY];
					q.push(make_pair(nextX, nextY));
				}
			}
		}
	}
	cout << dp[n - 1][m - 1];
	return 0;
}

---