[백준] 16946-벽 부수고 이동하기 4(C++)

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

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

 

사소한 부분에서 틀렸던 문제...

4일 동안 반례를 못찾고 시름시름 앓고 있었는데, bamgoesn 님께서 반례를 찾아주셨다. ㅠㅠ

다시 한번 감사드립니다. ㅠㅠ

 

구현 + bfs 문제입니다. 

어떻게 보면 시뮬레이션이기도 하고, bfs 심화같기도 한 문제.

 

 

접근방식

 

1. 우선 빈칸들의 좌표별로 이동가능한 값들을 저장해야한다.

이때, 구획별로 번호를 매겨주어서 벽을 허물었을 때, 중복으로 구획을 세지 않도록 한다.

 

2. 벽을 하나씩 부서보면서 해당하는 좌표의 값을 도출한다. 

 

문제풀이 

 

1. bfs를 통해서 빈 좌표별로 이동가능한 최대한 값을 도출한다.

 

2. 다시 한번 bfs를 통해 이번엔 구획에 해당하는 모든 값들에 이동가능한 값과 구획번호를 저장

 

3. 벽 좌표를 vector에 저장하고 하나씩 부서보면서 결과를 도출

이때, 구획번호가 중복이 되지 않겠끔 vector에 구획번호를 저장하면서 4방향을 모두 확인 

 

 

정답코드입니다. 

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

int n, m;
int arr[1001][1001] = { 0, };
vector <pair<int, int>> block;
int result[1001][1001] = { 0, };

int visited[1001][1001][2] = { 0, }; // 첨에는 이동 가능한 개수를 저장할거고, 두번째에는 고유 영역 값을 저장할 예정
int vis_cnt = 1; // 구획의 첫 번호는 1부터 

bool temp_v[1001][1001] = { 0, }; //난 bfs로 구현할거야, 얘는 탐색을 위해 사용할 배열

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


void bfs(int ty, int tx) {

	// 1. temp_v를 사용해서 이동 가능한 개수 파악하기
	int maxed = 1;
	temp_v[ty][tx] = 1;
	queue <pair<int, int>> que;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (temp_v[ny][nx] != 0)
				continue;
			temp_v[ny][nx] = 1;
			que.push(make_pair(ny, nx));
			maxed++;
		}
	}
	//cout << maxed << endl;

	// 2. visited에 이동가능한 개수와 자신의 구획번호를 입력하기 
	visited[ty][tx][0] = maxed;
	visited[ty][tx][1] = vis_cnt;
	que.push(make_pair(ty, tx));

	while (!que.empty()) {
		int cy = que.front().first;
		int cx = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++) {
			int ny = cy + y_ar[i];
			int nx = cx + x_ar[i];
			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] != 0)
				continue;
			if (visited[ny][nx][0] != 0)
				continue;
			visited[ny][nx][0] = maxed;
			visited[ny][nx][1] = vis_cnt;
			que.push(make_pair(ny, nx));
		}
	}



	vis_cnt++; //인덱스를 하나 올려준다.


}

int main() {
	ios_base::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; j++) {
			arr[i][j] = temp[j] - '0';
			if (arr[i][j] == 1)
				block.push_back(make_pair(i, j));
		}
	}

	//cout << block.size() << endl;

	//1. 영역별로 마킹하기!

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (temp_v[i][j] == 0 && arr[i][j] == 0) { // 벽이 아니고, 방문한 적이 없다면 탐색해야해!
				bfs(i, j);
			}

	/*
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cout << visited[i][j][1] << ' ';
		}
	cout << endl;
	}
	*/

	//2. 벽을 하나씩 부수면서 이동가능한 결과값을 도출하는 과정 

	vector <int> index; // index 값들을 임시 저장할 친구 
	for (int i = 0; i < block.size(); i++) {
		index.clear();
		int val = 1; //자신을 포함해야 하니 1 부터 시작한다. 
		
		int y = block[i].first;
		int x = block[i].second;

		for (int j = 0; j < 4; j++) {
			bool flag2 = true;
			int ny = y + y_ar[j];
			int nx = x + x_ar[j];

			if (ny < 0 || ny >= n || nx < 0 || nx >= m || arr[ny][nx] == 1)
				continue;
			for (int i = 0; i < index.size(); i++)
				if (visited[ny][nx][1] == index[i]) {
					flag2 = false;
					break;
				}
			if (flag2 == true) {
				val += visited[ny][nx][0];
				index.push_back(visited[ny][nx][1]);
			}
			
		}

		result[y][x] = val % 10;
	}


	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++)
			printf("%d", result[i][j]);
		printf("\n");
	}

}