[BOJ : 16932]모양 만들기
하악하악 커동빵디
[분류] : 탐색(DFS)
[조건]:
0으로 채워진 칸을 1로 바꾸었을때 연속적으로 존재하는 1의 개수가 가장 최대임을 찾으면 됩니다.
[과정] :
1)먼저 연속적으로 붙어있는 1로 채워진 칸들이 존재한다면 이들을 구분해 주기 위해 그룹화를 진행해야 된다.(그룹화를 진행 해야되는 이유는 '구현방법'에서 설명하겠습니다.)
2)그룹화가 진행되면서 동시에 그룹화 된 그룹들의 원소의 수를 담을 수 있는 배열에 하나씩 넣어줍니다.
3)그리고 나서 이제 본격적으로 정답을 구하기 위해 0으로 채워진 칸들을 확인해 가면서 '상,하,좌,우' 가 만약 0이 아니라면 그룹화된 number를 가져오고 원소의 수를 담았던 배열에서 해당 number에 들어있는 수를 가져옵니다.
4)이 과정을 반복하여 가장 큰 값을 도출해 내면 이 문제에 정답이 됩니다.
[구현 방법] :
이 문제 전 개인적으로 너무 힘들었습니다....아직 멀었다는 걸 느낀 문제입니다 ㅠㅠ
일단 처음에 만만히 보고 DFS로 풀면 되겠지 하고 풀었습니다.하지만 바로 '시간초과'가 발생 하더라구요.
1의 개수를 M이라고 했을때 시간 초과가 발생하는 이유는 바로 시간 복잡도가 약 O((NM)^2)이 될 수도 있기 때문입니다.
예를 들어 보겠습니다.
이런식으로 입력이 들어오게 된다면 매번 방문체크를 해주어야 되는 visit 함수를 초기화 하면서 진행하기에는 무리가 있습니다.따라서 이를 해결하기 위한 방법이 수들의 '그룹화'입니다.
방법은 이렇습니다.
1.연속적인 1들을 구분해 주기 위해 수들로 구분합니다.예제로 설명하면
이런식으로 입력이 들어오게 되면
이렇게 그룹화를 완성시켜 주면 됩니다.이 그룹화를 완성시켜 주는 과정은 평범하게 DFS를 이용해서 만들어 주면 되겠죠. 그러면서 동시에 그룹의 원소의 수를 배열에 미리 저장해 둡니다.
//그룹화 진행
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!visit[i][j] && map[i][j] == 1)
{
num = 0;
make_group(i, j, cnt++);
count_map[idx++] = num;
}
void make_group(int x, int y, int cnt)
{
visit[x][y] = true;
map[x][y] = cnt;
num++;
for (int i = 0; i < 4; i++)
{
int tdx = x + dx[i];
int tdy = y + dy[i];
if (tdx < 0 || tdx >= n || tdy < 0 || tdy >= m)continue;
if (!visit[tdx][tdy] && map[tdx][tdy] == 1)
make_group(tdx, tdy, cnt);
}
}2.이제 0인 칸을 찾아가면서 상,하,좌,우 를 탐색해 그룹화가 된 원소라면 그 원소의 수를 더해줍니다.
이때,한번 탐색이 끝나면 방문체크를 초기화를 해주어야 겠죠?이때 단순히 반복문이나 memset을 이용해서 초기화를 해버리면 시간초과가 발생해 버립니다.이유는 COUNT_SIZE 만큼 매번 초기화를 해버리면 엄청나게 많은 시간이 걸리기 때문이죠.따라서 이를 해결하기 위해 우리는 또 다른 배열(arr)을 선언해 줍니다.
이 배열에 탐색이 된 원소의 number를 저장해 주는 것이죠.이 배열은 상,하,좌,우 4군데만 확인해서 저장해 주면 되기 때문에 배열의 크기는 4이면 됩니다. 그리고 이 배열에 저장되어 있는 number만 초기화 해주면 되는 것 입니다.
소스를 보면 무슨 뜻인지 이해가 될 것입니다.(ㅠㅠ사실 자신이 없군요)
//그룹화된 수들을 합산
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (map[i][j] == 0)
{
int mx=0,find_count=0;
for (int k = 0; k < 4; k++)
{
int tdx = i + dx[k];
int tdy = j + dy[k];
if (tdx<0 || tdx>n || tdy<0 || tdy>m)continue;
int pos = map[tdx][tdy];
if (!count_visit[pos] && pos != 0)
{
mx += count_map[pos];
count_visit[pos] = true;
arr[find_count++] = pos;
}
}
ans = max(ans, mx);
for (int q = 0; q < find_count; q++)
count_visit[arr[q]] = false;
}
이렇게 해주면 주변에 있는 그룹화된 원소들의 수를 얻을 수 있고 여기에 자기 자신도 0->1 로 변경이 될 것 이니 +1을 더해주면 바로 정답이 됩니다.
[전체 소스]
#include<iostream>
#include<algorithm>
#include<cstring>
#define MAP_SIZE 1001
#define COUNT_SIZE 500010
using namespace std;
int n, m, num;
int dx[] = { 1,0,-1,0 }, dy[] = { 0,1,0,-1 };
int map[MAP_SIZE][MAP_SIZE], count_map[COUNT_SIZE];
int visit[MAP_SIZE][MAP_SIZE], count_visit[COUNT_SIZE];
void make_group(int x, int y, int cnt);
int main()
{
int cnt = 1, idx = 1, ans=0;
int arr[4], find_count;
cin >> n >> m;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> map[i][j];
//그룹화 진행
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (!visit[i][j] && map[i][j] == 1)
{
num = 0;
make_group(i, j, cnt++);
count_map[idx++] = num;
}
//그룹화된 수들을 합산
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (map[i][j] == 0)
{
int mx=0,find_count=0;
for (int k = 0; k < 4; k++)
{
int tdx = i + dx[k];
int tdy = j + dy[k];
if (tdx<0 || tdx>n || tdy<0 || tdy>m)continue;
int pos = map[tdx][tdy];
if (!count_visit[pos] && pos != 0)
{
mx += count_map[pos];
count_visit[pos] = true;
arr[find_count++] = pos;
}
}
ans = max(ans, mx);
for (int q = 0; q < find_count; q++)
count_visit[arr[q]] = false;
}
cout << ans+1 << "\n";
return 0;
}
void make_group(int x, int y, int cnt)
{
visit[x][y] = true;
map[x][y] = cnt;
num++;
for (int i = 0; i < 4; i++)
{
int tdx = x + dx[i];
int tdy = y + dy[i];
if (tdx < 0 || tdx >= n || tdy < 0 || tdy >= m)continue;
if (!visit[tdx][tdy] && map[tdx][tdy] == 1)
make_group(tdx, tdy, cnt);
}
}[틀린부분이나 어색한 표현이 있으면 마구마구 태클 바람!!]