백준 16946번 _벽 부수고 이동하기 4

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

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

 

1. 풀이방법

 

ex)

1	0	0	1
0	1	1	0
0	1	1	0
1	0	0	1

 표가 이렇게 되어있다고 하자.

 

1) 저 벽으로 감싸져 있는 공간끼리 빨간색은 1번 그룹, 파랑은 2번, 주황은 3번, 초록은 4번 이런식으로 묶는다.

 

2) 이제 이 그룹의 개수를 구해 따로 com[idx] 배열에다가 idx를 맞춰 넣는다. ( ex) 빨간색 com[1] = 2 )

나같은 경우에는 벽을 -1, 그룹type마다를 배열에다가 넣어줬다.

 

-1	1	1	-1
2	-1	-1	3
2	-1	-1	3
-1	4	4	-1

 

3) 이제 끝났다. 이제 전체배열을 돌며 벽이 있는 경우에 상하좌우에 그룹이 있다면, 그 그룹의 개수 + 자기자신을 더해주기만 하면된다.

 

 

2.코드

 

#include<iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int map[1002][1002];
int n, m;
int visit[1002][1002];
int resultmap[1002][1002];

void visitClear()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			visit[i][j] = 0;
}

int cnt;
void dfs(int y, int x, int comType)
{
	cnt++;
	map[y][x] = comType;

	//상하좌우 ㄱㄱ
	if (y - 1 >= 0 && map[y - 1][x] == 0 && visit[y - 1][x] == 0)
	{
		visit[y - 1][x] = 1;
		dfs(y - 1, x, comType);
	}
	if (y + 1 < n && map[y + 1][x] == 0 && visit[y + 1][x] == 0)
	{
		visit[y + 1][x] = 1;
		dfs(y + 1, x, comType);
	}
	if (x-1 >= 0 && map[y][x - 1] == 0 && visit[y][x -1] == 0)
	{
		visit[y][x - 1] = 1;
		dfs(y, x - 1, comType);
	}
	if (x +1 < m && map[y][x + 1] == 0 && visit[y][x + 1] == 0)
	{
		visit[y][x + 1] = 1;
		dfs(y, x + 1, comType);
	}
}

int main()
{
	cin >> n >> m;

	// make map
	//벽을 -1, 공간을 0
	string temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		for (int j = 0; j < m; j++)
		{
			if((temp[j] -'0') == 1)
				map[i][j] = -1;
		}
	}

	//컴포넌트 자리 찾아주기
	vector<int>com = {0};
	int comtype = 0; // 1부터시작
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (map[i][j] == 0)
			{
				//dfs
				comtype++;
				cnt = 0;
				dfs(i, j, comtype);
				com.push_back(cnt);
			}

	//순회하며 컴포넌트 합쳐주기
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			//벽일때
			if (map[i][j] == -1)
			{
				//상하좌우의 컴포넌트 구해준거 다합쳐주기, 중복 조심
				int sum = 0;
				set<int> used;

				if (i - 1 >= 0 && map[i - 1][j] != -1)
				{
					used.insert(map[i - 1][j]);
					sum += com[map[i - 1][j]];
				}
				if (i + 1 < n && map[i + 1][j] != -1 && used.count(map[i + 1][j])==0)
				{
					used.insert(map[i + 1][j]);
					sum += com[map[i + 1][j]];
				}
				if (j - 1 >= 0 && map[i][j - 1] != -1 && used.count(map[i][j - 1]) == 0)
				{
					used.insert(map[i][j - 1]);
					sum += com[map[i][j - 1]];
				}
				if (j + 1 < m && map[i][j + 1] != -1 && used.count(map[i][j + 1]) == 0)
				{
					used.insert(map[i][j + 1]);
					sum += com[map[i][j + 1]];
				}
				resultmap[i][j] = (sum + 1)%10;
			}
		}
	}
	
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cout << resultmap[i][j];
		}
		cout << '\n';
	}

	
	return 0;
}

 

 

3. 후기

 

처음에는 그냥 dfs문제인줄 알고 풀어 계속 시간초과가 났다..

최근 계속 문제를 이해를 잘못하고 무작정 푸는데 이게 잘 고쳐지지않네 ㅠㅠ