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

문제

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다.

각각의 벽에 대해서 다음을 구해보려고 한다.

• 벽을 부수고 이동할 수 있는 곳으로 변경한다.
• 그 위치에서 이동할 수 있는 칸의 개수를 세어본다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다.

 

출력

맵의 형태로 정답을 출력한다. 원래 빈칸인 곳은 0을 출력하고, 벽인 곳은 이동할 수 있는 칸의 개수를 10으로 나눈 나머지를 출력한다.

 

코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

int N;
int M;
int zero_area;			// 영역 번호
int d[] = {1, -1, 0, 0};	// 상하좌우로 이동
int map[1001][1001];		// 맵 (0: 빈칸, 1: 벽, 2 이상: 빈칸의 영역 번호)
bool visit[1001][1001];		// 방문 여부
vector<int> zero;		// i번째 영역을 이루는 칸의 수

// (n, m)에서 시작하는 새로운 영역을 찾음
// 영역을 이루는 칸의 수를 저장하고 다음 영역을 위해 영역 번호를 증가시킴
void bfs(int n, int m)
{
	queue< pair<int, int> > q;
	int i, dn, dm, cnt = 0;

	q.push(make_pair(n, m));
	visit[n][m] = true;
	while (!q.empty())
	{
		cnt++;
		n = q.front().first;
		m = q.front().second;
		q.pop();
		map[n][m] = zero_area;
		{
			for (i = 0; i < 4; i++)
			{
				dn = n + d[i];
				dm = m + d[3 - i];
				if (dn < 0 || dn >= N || dm < 0 || dm >= M)
					continue;
				if (map[dn][dm] || visit[dn][dm])
					continue;
				q.push(make_pair(dn, dm));
				visit[dn][dm] = true;
			}
		}
	}
	zero.push_back(cnt);
	zero_area++;
}

// 벽을 부수고 상하좌우로 이동할 수 있는 칸의 수를 리턴
// 동일한 영역을 중복으로 더하지 않기 위해 check에 표시
int move(int n, int m)
{
	vector<bool> check;
	int i, dn, dm, res = 1;

	check.resize(zero.size(), false);
	for (i = 0; i < 4; i++)
	{
		dn = n + d[i];
		dm = m + d[3 - i];
		if (dn < 0 || dn >= N || dm < 0 || dm >= M)
			continue;
		if (check[map[dn][dm]])
			continue;
		res += zero[map[dn][dm]];
		check[map[dn][dm]] = true;
	}
	return res;
}

int main()
{
	int i, j;
	string s;

	cin >> N >> M;
	for (i = 0; i < N; i++)
	{
		cin >> s;
		for (j = 0; j < M; j++)
			map[i][j] = s[j] - '0';
	}
    
        // 0과 1은 입력으로 주어지는 맵을 구성하는 숫자이므로 사용하지 않음
	zero.push_back(0);
	zero.push_back(0);
	zero_area = 2;
    
        // 0으로 이루어진 모든 영역을 확인
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (!map[i][j])
				bfs(i, j);
		}
	}
    
        // 정답 출력
	for (i = 0; i < N; i++)
	{
		for (j = 0; j < M; j++)
		{
			if (map[i][j] == 1)
				cout << move(i, j) % 10;
			else
				cout << 0;
		}
		cout << endl;
	}
	return 0;
}

 

링크

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

inbdni/Baekjoon