백준 2206번 벽 부수고 이동하기 C++

BFS문제

벽을 한 번 부술 수 있다.

 

queue<pair<pair<int, int>, bool>> q;

 

pair형을 저장하는 queue를 생성해

첫 번째 요소 pair<int, int>에는 좌표 값을, 두 번째 요소 bool 에는 벽을 부쉈는지 여부를 저장했다.

 

 

if (cycleSize == 0) {
	++cnt;
	cycleSize = q.size();
}

q.pop();
--cycleSize;

 

몇 번 이동했는지 세기 위해 cycleSize라는 변수를 생성해 queue.size()를 넣어주고,

queue를 pop할 때마다 -1

cycleSize가 0이 되면 이동횟수(cnt)를 +1 하고 다시 cycleSize에 queue의 size()를 채워줬다.

 

 

visited 라는 2차원 bool 배열을 하나만 만들어서 제출했더니 15%에서 막혔다.

visited하나만 있을 경우 반례

6 5

00000

11110

00000

01111

01111

00010

n, m 에 도착할 수 있어야하지만 결과가 -1(실패)이 나왔다.

 

그래서 breakVisited라는 bool 2차원배열을 하나 더 생성해,

벽을 부쉈을 때와 부수지 않았을 때 구별해서 visited를 확인해줬다.

 

 

전체코드

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

int n, m;
char arr[1001][1001]{};
bool visited[1001][1001]{};
bool breakVisited[1001][1001]{};

int BFS(int startY, int startX) {
	if (startY == n - 1 && startX == m - 1)
		return 1;

	queue<pair<pair<int, int>, bool>> q; // bool - 벽을 부쉈는지 여부
	q.push({ {startY, startX}, 0 });

	visited[startY][startX] = true;
	breakVisited[startY][startX] = true;

	int dy[4] = { 1, -1, 0, 0 };
	int dx[4] = { 0, 0, -1, 1 };
	int cnt = 0;
	int cycleSize = 0;

	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		bool isBreakWall = q.front().second;

		if (cycleSize == 0) {
			++cnt;
			cycleSize = q.size();
		}

		q.pop();
		--cycleSize;

		for (int i = 0; i < 4; ++i) {
			int ny = y + dy[i];
			int nx = x + dx[i];

			if (ny < 0 || nx < 0 || ny >= n || nx >= m)
				continue;
			if ((isBreakWall && breakVisited[ny][nx])
				|| (!isBreakWall && visited[ny][nx]))
				continue;

			if (ny == n - 1 && nx == m - 1)
				return cnt + 1;

			if (isBreakWall)
				breakVisited[ny][nx] = true;
			else
				visited[ny][nx] = true;

			if (arr[ny][nx] == '1' && !isBreakWall)
				q.push({ {ny, nx}, 1 });
			else if (arr[ny][nx] == '0') {
				if (!isBreakWall)
					q.push({ {ny,nx}, 0 });
				else
					q.push({ {ny,nx}, 1 });
			}
		}
	}
	return -1;
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

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

	cout << BFS(0, 0);

	return 0;
}

 

 

 

 

https://www.acmicpc.net/problem/2206