[백준 16946번 C/C++] 벽 부수고 이동하기 4

 

[백준 16946번 C/C++] 벽 부수고 이동하기 4

 

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

16946번: 벽 부수고 이동하기 4

---

 

 

해결전략

 

너비우선탐색 BFS

 

 

풀이전략

1. 0 위치 한 곳에서 BFS를 실행한다.
   • 인접한 0을 모두 방문하고 카운팅(cnt)하고 방문체크한다.

     • 	// 빈 공간이고 방문하지 않았다면
           if (v[ny][nx] == 0 && ch[ny][nx] == 0) {
               Q.push({ ny, nx });
               ch[ny][nx] = 1;
               cnt++;
           }

   • 인접한 wall(1이상의 값의 위치)을 새로운 큐(wallQ)에 담고 방문체크한다. 

     • 	// 벽이고 방문하지 않았다면
           else if (v[ny][nx] >= 1 && visited_Wall[ny][nx] == 0) {
               wallQ.push({ ny, nx });
               visited_Wall[ny][nx] = 1; // 벽 방문 체크
           }​

   • 인접한 wall에 cnt한 값을 더해준다. 

     • 	// 인접한 wall에 방금 방문한 0들을 카운트(cnt)한 값을 더함(=벽에 인접한 빈 공간의 개수를 더함)
       	while(!wallQ.empty())
       	{
       		int yy = wallQ.front().first;
       		int xx = wallQ.front().second;
       		wallQ.pop();
       
       		v[yy][xx] += cnt;  // 벽에 인접한 빈 공간의 개수를 더함
       		visited_Wall[yy][xx] = 0; // 벽 방문 체크를 초기화
       	}

2. 방문한적이 없는 0 위치에서 위 과정을 반복한다

	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) 
		{
			if (v[y][x] == 0 && ch[y][x] == 0) {
				BFS(y, x);
			}
		}
	}

 

---

 

정답 코드

 

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

int dirY[4] = { -1, 0, 1, 0 };
int dirX[4] = { 0, -1, 0, 1 };

int n, m;
vector<vector<int>> v;
vector<vector<int>> ch; // 방문 여부를 체크할 벡터 
vector<vector<int>> visited_Wall; // 벽에 대한 방문 여부를 체크할 벡터

void BFS(int y, int x) // BFS를 이용해서 벽에 인접한 빈 공간을 탐색하고, 그 크기를 구하는 함수
{
	queue<pair<int, int>> Q;
	Q.push({ y, x });
	ch[y][x] = 1; // 방문 체크

	int cnt = 1; // 방문한 빈 공간의 개수

	queue<pair<int, int>> wallQ; // 벽의 위치를 저장할 큐

	while (!Q.empty())
	{
		int y = Q.front().first;
		int x = Q.front().second;
		Q.pop();

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

			if (ny < 0 || n <= ny || nx < 0 || m <= nx) continue;

			// 빈 공간이고 방문하지 않았다면
			if (v[ny][nx] == 0 && ch[ny][nx] == 0) {
				Q.push({ ny, nx });
				ch[ny][nx] = 1;
				cnt++;
			}
			// 벽이고 방문하지 않았다면
			else if (v[ny][nx] >= 1 && visited_Wall[ny][nx] == 0) {
				wallQ.push({ ny, nx });
				visited_Wall[ny][nx] = 1; // 벽 방문 체크
			}
		}
	}

	// 인접한 wall에 방금 방문한 0들을 카운트(cnt)한 값을 더함(=벽에 인접한 빈 공간의 개수를 더함)
	while(!wallQ.empty())
	{
		int yy = wallQ.front().first;
		int xx = wallQ.front().second;
		wallQ.pop();

		v[yy][xx] += cnt;  // 벽에 인접한 빈 공간의 개수를 더함
		visited_Wall[yy][xx] = 0; // 벽 방문 체크를 초기화
	}
}

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

	cin >> n >> m;
	v.resize(n, vector<int>(m));
	ch.resize(n, vector<int>(m)); 
	visited_Wall.resize(n, vector<int>(m));

	string input;
	for (int y = 0; y < n; y++) {
		cin >> input;
		for (int x = 0; x < m; x++) {
			v[y][x] = input[x] - '0';
		}
	}

	// 모든 빈 공간에 대해 BFS 실행
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) 
		{
			if (v[y][x] == 0 && ch[y][x] == 0) {
				BFS(y, x);
			}
		}
	}


	// 출력
	for (int y = 0; y < n; y++) {
		for (int x = 0; x < m; x++) {
			cout << v[y][x] % 10;
		}
		cout << "\n";
	}

	return 0;
}

 

 

---