🙇‍♀️[Gold II] 벽 부수고 이동하기 4 - 16946

문제 링크

성능 요약

메모리: 17004 KB, 시간: 140 ms

분류

너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2024년 3월 1일 14:32:31

문제 설명

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

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

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

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

입력

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

출력

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

🚀풀이

이 문제를 처음에 도전할 때는 문제의 조건의 순서대로 해결하려고 했다.

벽 위치에서 BFS를 돌려서 0의 개수를 세고 출력하는 방식이였는데 시간초과가 났다.

다른 방식을 이용해야하는데 0의 개수를 미리 세어 놓고 벽을 부술 때 상하좌우를 체크하여 0들을 한꺼번에 계산하는 방식이다.

이 때 중복된 영역인지 아닌지 알기 위해서 0들의 영역당 인덱스를 붙여야한다.
그 인덱스를 zeroAreaIdx 로 이름지었고, 0들의 영역은 zeroArea 로 지었다.
zeroArea 는 값으로 인덱스만 가지고 있다. 실제로 0의 개수는 zeroAreaZeroCount란 이름으로 계산한다.

BFS를 돌릴 때 위의 변수들을 주의해서 보자.

그리고 다른 사람들은 나중에 1인 벽인 공간에서 상하좌우를 계한할 때 다 set을 이용했는데 며칠걸린 이 문제를 그냥 다른사람처럼 풀기 싫었다. (그냥 미련한 바보임)

난 그냥 set을 안쓰고 계산해서 체크했다.
아무튼 맞았으면 된거지 ㅇㅅㅇ

image

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>

using namespace std;

// 시간초과가 뜨지 않게 변환

int n, m, zeroAreaIdx = 0;
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
int board[1111][1111];
int zeroArea[1111][1111];
int visited[1111][1111];
vector<int> zeroAreaZeroCount;
int BFS(int y, int x)
{
	int res = 0;
	queue<pair<int, int>> q;
	q.push({ y, x });
	visited[y][x] = 1;
	zeroArea[y][x] = zeroAreaIdx;

	pair<int, int> here;
	while (q.empty() == false)
	{
		here = q.front();
		q.pop();
		res++;

		for (int i = 0; i < 4; ++i)
		{
			int ny = here.first + dy[i];
			int nx = here.second + dx[i];

			if (ny < 1 || nx < 1 || ny > n || nx > m)
				continue;
			if (visited[ny][nx] == 1)
				continue;
			if (board[ny][nx] == 1)
				continue;

			q.push({ ny, nx });
			visited[ny][nx] = 1;
			zeroArea[ny][nx] = zeroAreaIdx;
		}
	}

	zeroAreaZeroCount.push_back(res);
	return res % 10;
}

void solve()
{
	// 입력값 받기
	cin >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		string str;
		cin >> str;
		for (int j = 1; j <= m; ++j)
		{
			board[i][j] = str[j - 1] - '0';
		}
	}

    // 0번 인덱스랑 곂치니까 -1로 초기화
	::memset(zeroArea, -1, sizeof(zeroArea));

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (board[i][j] == 0 && visited[i][j] == 0)
			{
				BFS(i, j);
                // 인덱스 증가 시켜서 다른 그룹으로 만들기
				zeroAreaIdx++;
			}
		}
	}

	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= m; ++j)
		{
			if (board[i][j] == 1)
			{
				vector<int> cache(4, -1);
				for (int k = 0; k < 4; ++k)
				{
					int ny = i + dy[k];
					int nx = j + dx[k];

					cache[k] = zeroArea[ny][nx];
				}
				sort(cache.begin(), cache.end());
				cache.push_back(-1);
				int res = 0;
				for (int k = 0; k < 4; ++k)
				{
					if (cache[k] == -1)
						continue;
					if (cache[k] == cache[k + 1])
						continue;
					res += zeroAreaZeroCount[cache[k]];
				}
				::cout << (res + 1) % 10;
			}
			else
				::cout << 0;
		}
		::cout << '\n';
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	::cout.tie(NULL);
	freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고