백준 16946 c++ 벽 부수고 이동하기 4

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

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

문제

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

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

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

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

입력

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

출력

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

---

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

int N, M;
int map[1001][1001];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
bool visit[1001][1001];

void bfs(int row, int col)
{
	queue<pair<int, int>> q;
	vector<pair<int, int>> v;
	q.push(make_pair(row,col));
	visit[row][col] = true;
	int result = 1;
	while (!q.empty())
	{
		int nowX = q.front().first;
		int nowY = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nextX = nowX + dx[i];
			int nextY = nowY + dy[i];
			if ((nextX < 0 || nextX >= N) || (nextY < 0 || nextY >= M))//범위 벗어나면 스킵
				continue;

			if (map[nextX][nextY] == 0 && visit[nextX][nextY] == false) //다음 칸이 방문한 적 없는 통로이면
			{
				q.push(make_pair(nextX, nextY));
				visit[nextX][nextY] = true;
				result++;
			}
			if (map[nextX][nextY] != 0 && visit[nextX][nextY] == false)//다음 칸이 방문한 적 없는 벽이라면
			{
				v.push_back(make_pair(nextX, nextY));
				visit[nextX][nextY] = true;
			}
		}
	}
	for (int i = 0; i < v.size(); i++)
	{
		map[v[i].first][v[i].second] += result;
		visit[v[i].first][v[i].second] = false;
	}
}

int main()
{
	//입력
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &map[i][j]); //공백이 없어도 숫자 하나씩만 입력받기
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			if (map[i][j] != 0)//현재칸이 통로가 아니면 스킵
				continue;
			if (visit[i][j])//현재칸이 0이지만 방문했다면 스킵
				continue;
			bfs(i, j); //0이고 방문안한 곳에서 bfs 실행
		}
	}
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			cout << map[i][j] % 10;
		}
		cout << '\n';
	}
}

1. map을 탐색하며 0인 부분에서 bfs실행

2. bfs실행하여 상하좌우 탐색하며

2-1 => 0을 만났을 때 count++

2-2 => 1을 만났을 때 vector안에 벽 정보를 넣음

3.  bfs함수가 끝날 때 bfs에서 탐색한 0들에 인접한 벽에 대해 (2-2에서 vector에 넣었던 벽들) 지금까지  count값을 더해준다.