<Baekjoon> #2206 BFS_벽 부수고 이동하기 c++

#2206 벽 부수고 이동하기
#1450 연구소 문제와 비슷해서 그때 풀었던 것과 비슷하게 풀었는데 시간 초과가 났다.

풀이1

• 벽은 부수거나, 1개만 부수거나이므로 처음에는 벽을 부수지 않았을 때 주어진 map 그대로 해서 distance를 구한다

• 다음 map의 모든 정점을 순회하면서 WALL==1일 경우 해당 부분을 PATH=0으로 바꾸어주고 bfs 탐색 후 다시 WALL=1로 바꾸어 준다. (탐색을 할 때마다 최소 distance를 갱신해준다)

• 참고로 처음 map을 받을 때 엔터로 하나씩 띄우면서 받는줄 알아서 잘못 짰다. 아래 코드는 테스트 케이스는 통과했지만 백준에서 통과는 안 됐다

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
const int MAX = 1001;

int n, m;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1, 0,0 };
int dist[MAX][MAX];
int minDist = 0x7fffffff;

void  bfs(vector<vector<int>> &map) {
	queue<pair<int, int>> q;
	q.push(make_pair(1, 1));
	dist[1][1] = 1;

	while (!q.empty()) {
		int cur_y = q.front().first;
		int cur_x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

			if (nx_y <= 0 || nx_x <= 0 || nx_y > n || nx_x > m) continue;
			if (dist[nx_y][nx_x] == 0 && map[nx_y][nx_x]==0) {
				q.push(make_pair(nx_y, nx_x));
				dist[nx_y][nx_x] = dist[cur_y][cur_x] + 1;
			}
		}
	}
	if (dist[n][m]!=0) minDist = min(minDist, dist[n][m]);
}

int main() {
	cin >> n >> m;
	vector<vector<int>> map(n+1, vector<int>(m+1));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> map[i][j];
	memset(dist, 0, sizeof(dist));
	bfs(map);
	memset(dist, 0, sizeof(dist));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 1) {
				map[i][j] = 0;
				bfs(map);
				memset(dist, 0, sizeof(dist));
				map[i][j] = 1;
			}
		}
	}
	if (minDist == 0x7fffffff)
		cout << -1 << endl;
	else cout << minDist << endl;
	return 0;
}

풀이2

• queue<pair<pair<int, int>, pair<int, int>>> q를 두어 처음 한 쌍은 (y,x)로 현재 좌표를 뜯하고, 다음 쌍은 (break-벽을 부순 횟수 0 or 1, count-distance)이다.

• visited[][][2]로 만들고visited[y][x][0]는 벽을 한 번도 부수지 않았을 때 좌표(y,x)방문 여부, visited[y][x][1]는 벽을 한 번 부쉈을 때 좌표(y,x)방문 여부를 나타낸다

• 다음 위치가 WALL==1이고, 벽을 한 번도 부순 적이 없다면 (break==0) 벽을 부수어 이 지점을 방문한다

  if (map[nx_y][nx_x] == WALL && brk==0) {
  				visited[nx_y][nx_x][brk + 1] = true;
  				q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt+1)));
  			}

• 다음 위치가 PATH==0이고, 이 점을 방문한 적이 없다면 이 지점을 방문한다

  else if (map[nx_y][nx_x] == PATH && visited[nx_y][nx_x][brk] == false) {
  	visited[nx_y][nx_x][brk] = true;
  	q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1)));
  }

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

const int MAX = 1000;
const int WALL = 1;
const int PATH = 0;
vector<vector<int>> map;
int visited[MAX][MAX][2];
int n, m;
int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };

int bfs() {
	queue<pair<pair<int, int>, pair<int, int>>> q;
	q.push(make_pair(make_pair(0, 0), make_pair(0, 1)));
	visited[0][0][0] = true;

	while (!q.empty()) {
		int cur_y = q.front().first.first;
		int cur_x = q.front().first.second;
		int brk = q.front().second.first;
		int cnt = q.front().second.second;
		q.pop();

		if (cur_y == n - 1 && cur_x == m - 1) return cnt;

		for (int i = 0; i < 4; i++) {
			int nx_y = cur_y + dy[i];
			int nx_x = cur_x + dx[i];

			if (nx_y < 0 || nx_x < 0 || nx_y >= n || nx_x >= m) continue;
			if (map[nx_y][nx_x] == WALL && brk==0) {
				visited[nx_y][nx_x][brk + 1] = true;
				q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk+1, cnt+1)));
			}
			else if (map[nx_y][nx_x] == PATH && visited[nx_y][nx_x][brk] == false) {
				visited[nx_y][nx_x][brk] = true;
				q.push(make_pair(make_pair(nx_y, nx_x), make_pair(brk, cnt + 1)));
			}
		}
	}
	return -1;
}
int main() {
	cin >> n >> m;
	map = vector<vector<int>> (n, vector<int > (m));
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		for (int j = 0; j < m; j++) {
			int tmp2 = tmp[j] - '0';
			map[i][j] = tmp2;
		}
	}
	cout << bfs() << endl;
	return 0;
}