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

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

1261번: 알고스팟

 

bfs문제인데 조금 꼬아놓은 bfs였습니다! 

최단 경로이동이 아니라 벽을 최소로 부수며 이동할때의 벽을 최소 몇 개 부수어야 하는지이기 때문에 방문 배열이 총 2개가 필요합니다.

 

1. 방문했는지 여부를 판단해주는 배열

2. 방문했다면 해당 경로로 최소 몇번만에 도달할 수 있는 표시하는 배열

 

쉬운문제였기 때문에 바로 정답코드입니다.

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int m, n;
int arr[101][101] = { 0, };
int visited[101][101][2] = { 0, };

int y_ar[4] = { 0,0,1,-1 };
int x_ar[4] = { 1,-1,0,0 };

void bfs() {

	queue <pair<int, int>> que;
	que.push(make_pair(1, 1));
	if (arr[1][1] == 1) visited[1][1][0] = 1, visited[1][1][1] = 1;
	else visited[1][1][0] = 1, visited[1][1][1] = 0;

	while (!que.empty()) {

		int yy = que.front().first;
		int xx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int y = yy + y_ar[i];
			int x = xx + x_ar[i];

			if (y >= 1 && y <= n && x >= 1 && x <= m) {
				if (visited[y][x][0] == 0) { //방문한적 없어
					visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
					que.push(make_pair(y, x));	
				}
				else { // 방문했다면, 
					if (visited[y][x][1] > (visited[yy][xx][1] + arr[y][x])) { 
						visited[y][x][0] = 1, visited[y][x][1] = visited[yy][xx][1] + arr[y][x];
						que.push(make_pair(y, x));
					}
					

				}
			}

		}

	}

}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++){
			string temp;
			cin >> temp;
			for (int j = 1; j <= m; j++)
				arr[i][j] = temp.at(j - 1) - '0';
	}

	
	bfs();

	
	cout << visited[n][m][1] << "\n";
}

 visited[yy][xx][1] + arr[y][x]는 지금까지 벽을 부순횟수 더하기 현재 벽이 있다면 부수고 들어가고(+1) 아니면(+0)을 하는 코드입니다.