반응형
문제
Garage game
접근방법
1) 접근 사고
크게 각각의 모든 경우를 탐색하는 백트래킹, 각 영역을 확인하는 BFS, 그리고 어느정도의 높은 구현 능력을 요구하는 문제였다.
2) 시간 복잡도
n이 적고 문제에서 모든 경우의 탐색을 요구해야하는 문제였다.
3) 배운 점
처음에 BFS로 먼저 탐색하고 직사각형의 규모를 측정해줄려고 했었다.
그런데 BFS 코드의 로직을 보면 탐색후 0으로 값을 변환해준다.
이 과정을 알아내기 위해 디버깅 하는데 정말 많은 시간을 소모했다.
개인적으로 구현 능력실력이 많이 올라온거 같은데 디버깅 실력이 개인적으로 느끼기에 정말 최악인거 같다.
4) PS
2차원 배열을 람다식에 넘겨줄 경우 값이 정확히 안넘어간다 주의하자
정답 코드
/*
1.DFS함수를 통해서 모든 과정 탐색하기
2.먼저 직사각형의 규모를 구해준다.
3.BFS를 통해 없앨 규모를 구해준다.
4.없애버린 차동차를 밑으로 내린다
5.값을 반환하고 3번째 과정이 되면 최고값을 갱신한다.
*/
/*
2
1 1
2 2
1 1
3 3
4 4
1 2
15
3
8 5 1
9 6 1
10 7 1
11 1 3
12 1 3
13 1 3
1 2 2
1 2 2
1 2 2
36
*/
#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
using namespace std;
const int MAX = 16;
int board[MAX*3][MAX];
int n;
int moveY[] = { -1, 1, 0, 0 };
int moveX[] = { 0, 0, -1, 1 };
int maxValue = INT_MIN;
int BFS(int y, int x, int tmpboar[MAX*3][MAX])
{
//직사각형의 크기를 구하는 과정
int height = 1;
int width = 1;
for (int i = 0; i < 4; i++)
{
int nextY = y;
int nextX = x;
while (1)
{
nextY += moveY[i];
nextX += moveX[i];
if (nextY >= 0 && nextY < n * 3 && i >= 0 && i <= 1 && tmpboar[y][x] == tmpboar[nextY][nextX] && tmpboar[y][x] != 0)
height++;
else if (nextX >= 0 && nextX < n && i >= 2 && i <= 3 && tmpboar[y][x] == tmpboar[nextY][nextX] && tmpboar[y][x] != 0)
width++;
else
break;
}
}
//BFS를 통한 규모 측정
bool visited[MAX*3][MAX];
memset(visited, false, sizeof(visited));
queue<pair<int, int>> q;
q.push({ y, x });
visited[y][x] = true;
int originalValue = tmpboar[y][x];
int cnt = 0;
while (!q.empty())
{
int curY = q.front().first;
int curX = q.front().second;
q.pop();
tmpboar[curY][curX] = 0;
for (int i = 0; i < 4; i++)
{
int nextY = curY + moveY[i];
int nextX = curX + moveX[i];
if (nextY >= 0 && nextY < n * 3 && nextX >= 0 && nextX <= n)
if (tmpboar[nextY][nextX] == originalValue && !visited[nextY][nextX])
{
q.push({ nextY, nextX });
visited[nextY][nextX] = true;
}
}
cnt++;
}
//덱을 활용한 위에있는 차들을 아래로 모두 끌어 내리는 과정
deque<int> tmpq;
for (int i = 0; i < n; i++)
{
for (int j = n * 3 - 1; j >= 0; j--)
{
if (tmpboar[j][i])
tmpq.push_back(tmpboar[j][i]);
tmpboar[j][i] = 0;
}
int idx = n * 3 - 1;
while (!tmpq.empty())
{
int data = tmpq.front();
tmpq.pop_front();
if (!tmpboar[idx][i])
{
tmpboar[idx][i] = data;
idx--;
}
else
{
idx--;
tmpq.push_front(data);
}
}
}
return cnt + (height * width);
}
void DFS(int y, int x, int cnt, int sum, int tmpboard[][MAX])
{
if (cnt == 3)
{
maxValue = max(maxValue, sum);
return;
}
for (int i = n * 2; i < n * 3; i++)
for (int j = 0; j < n; j++)
{
if (tmpboard[i][j] == 0)
continue;
int tmptmpboard[MAX*3][MAX];
memcpy(tmptmpboard, tmpboard, sizeof tmptmpboard);
int nextValue = sum + BFS(i, j, tmptmpboard);
DFS(i, j, cnt + 1, nextValue, tmptmpboard);
}
};
int main(void)
{
fastio;
cin >> n;
for (int i = 0; i < n * 3; i++)
for (int j = 0; j < n; j++)
cin >> board[i][j];
for (int i = n * 2; i < n * 3; i++)
for (int j = 0; j < n; j++)
{
int tmpboard[MAX*3][MAX];
bool visited[MAX*3][MAX];
memset(visited, false, sizeof(visited));
memcpy(tmpboard, board, sizeof(tmpboard));
int sum = BFS(i, j, tmpboard);
DFS(i, j, 1, sum, tmpboard);
}
cout << maxValue << "\n";
}
반응형