[백준 16946] 벽 부수고 이동하기 4

문제 링크 => 16946번: 벽 부수고 이동하기 4 (acmicpc.net)

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

---

그래프 탐색을 이용한 문제이다.

 

먼저 이동할 수 있는 지점(0으로 구성된 곳)에 대해서 값을 먼저 세팅하도록 하였다.

 

문제에 있는 예시 2로 설명하자면 다음과 같다.

 

4 5

11001

00111

01010

10101

 

이때, 1은 이동할 수 없는 지점(벽)이므로 0으로 세팅하고 0으로 된 지점에서 그 다음 0으로 이동할 수 있는지를 파악하도록 한다.

 

--- dp[N][M] ---

00220

33000

30101

01010

 

이때 같은 그룹임을 파악하기 위해서 visited 배열에서 방문 처리를 할 때, 1, 2, 3, ... 이런식으로 값을 다음과 같이 매겨주도록 하였다.

 

--- visited[N][M] ---

00110

22000

20304

05060

 

답을 구하기 위한 모든 세팅이 끝났다.

 

이제 dp, visited 배열을 통해서 벽인 지점에서 상하좌우 0인 지점에 대해서 dp 값을 더해주는데 같은 그룹을 두번 더하는 일이 없도록 visited 배열을 잘 활용하면 된다.

 

풀이 code

 

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int dp[1001][1001];
int Map[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int visited[1001][1001];
int N, M, visitCnt;


void input() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < M; j++) {
			Map[i][j] = s[j] - '0';
		}
	}
}

void setDp(int startX, int startY) {
	visitCnt++;
	int moveCnt = 1;
	queue<pair<int, int>> tmpQ;
	tmpQ.push({ startX,startY });
	queue<pair<int, int>> q;
	q.push({startX,startY});
	visited[startX][startY] = visitCnt;

	while (!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		int cnt = q.front().second;
		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int nextX = x + dx[i];
			int nextY = y + dy[i];
			if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) {
				if (Map[nextX][nextY] == 0 && !visited[nextX][nextY]) {
					tmpQ.push({ nextX,nextY });
					moveCnt++;
					q.push({nextX,nextY});
					visited[nextX][nextY] = visitCnt;
				}
			}
		}
	}

	while (!tmpQ.empty()) {
		int x = tmpQ.front().first;
		int y = tmpQ.front().second;
		tmpQ.pop();
		dp[x][y] = moveCnt;
	}

}

void solve() {

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j] == 0 && !visited[i][j]) setDp(i, j);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j]) {
				map<int, int> m;
				dp[i][j] = 1;
				for (int k = 0; k < 4; k++) {
					int nextX = i + dx[k];
					int nextY = j + dy[k];
					if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < M) {
						if (!Map[nextX][nextY] && !m[visited[nextX][nextY]]) {
							m[visited[nextX][nextY]] = 1;
							dp[i][j] += dp[nextX][nextY];
						}
					}
				}
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (Map[i][j]) cout << dp[i][j] % 10;
			else cout << 0;
		}
		cout << endl;
	}

}

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

	input();
	solve();

	return 0;
}