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

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

1261번: 알고스팟

BFS를 이용한 문제였습니다.

문제 조건

출력 예시

Cnt[X][Y] 배열을 통해, (1,1) 에서 시작해서 (X,Y)까지 왔을때, 벽을 부순 최소 횟수를 저장했습니다.

탐색을 하기전에, Cnt[X][Y] 배열에는 큰 값을 저장하여, 최솟값을 저장할 수 있도록 합니다.

(X,Y)를 오는 경우는 4가지가 있는데,

1. (X,Y)가 벽이 아니며, 이전에 오지 않았을 경우

2. (X,Y)가 벽이 아니며, 이전에 왔을 경우 + 해당 경우가 이전 경우보다 벽을 부순 횟수가 적을 때

3. (X,Y)가 벽이며, 이전에 오지 않았을 경우

4. (X,Y)가 벽이며, 이전에 왔을 경우 + 해당 경우가 이전 경우보다 벽을 부순 횟수가 적을 때

 

해당 경우에서는 queue에 다시 넣어 탐색을 해주면 됩니다.

이때 주의할 점은, (M,N)에 도착해도 탐색을 끝내면 안됩니다. -> 해당 경우가 최솟값이라는 것을 장담할 수 없음.

 

따라서 탐색이 모두 끝난 뒤에 cnt[M][N]의 값을 return 해주면 됩니다.

 

문제 접근 방법

1.  cnt 배열을 모두 큰값으로 초기화 해준다.

2.  (1,1) 에서 시작해, 4방향 탐색을 한다.

3. 4가지 경우를 만족하는 경우, queue에 넣어줘 탐색을 이어간다.

4. 탐색이 모두 끝난 경우 cnt[M][N] 값을 return 한다.

 

 

자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M;
int map[101][101];
int check[101][101];
int cnt[101][101];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

int bfs() {
	queue<pair<int, int>> q;
	q.push(make_pair(1, 1));
	check[1][1] = 1;
	cnt[1][1] = 0;
	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && xx <= M && yy >= 1 && yy <= N) {
				if (map[xx][yy] == 0) {
					if (check[xx][yy] == 0) {
						check[xx][yy] = 1;
						cnt[xx][yy] = cnt[x][y];
						q.push(make_pair(xx, yy));
					}
					else {
						if (cnt[xx][yy] > cnt[x][y]) {
							cnt[xx][yy] = cnt[x][y];
							q.push(make_pair(xx, yy));
						}
					}
				}
				else {
					if (check[xx][yy] == 0) {
						check[xx][yy] = 1;
						cnt[xx][yy] = cnt[x][y] + 1;
						q.push(make_pair(xx, yy));
					}
					else {
						if (cnt[xx][yy] > cnt[x][y] + 1) {
							cnt[xx][yy] = cnt[x][y] + 1;
							q.push(make_pair(xx, yy));
						}
					}
				}
			}
		}
	}
	return cnt[M][N];
}

void reset_cnt() {
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			cnt[i][j] = 100000000;
		}
	}
}

void solve() {
	reset_cnt();
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%01d", &map[i][j]);
		}
	}
	solve();
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!