https://softeer.ai/practice/6276/history?questionType=ALGORITHM
문제 요약
- 애니팡 같은 게임... 격자안에서 선택한 색과 상/하/좌/우 색이 같은 자동차를 모두 제거 후 빈칸은 채우는 문제..
- 임의의 점을 선택 후 차량 제거, 최종적(총 3회)으로 사라진 자동차의 개수가 점수인데, 최대 점수를 출력하라고 함.....
알고리즘
- array의 row에는 세로를 넣고, col에는 가로를 넣는다 -> 이래야 자동차를 이동하기 편리할 거 같음..
- 우선 DFS & backtracking를 사용해야 할거 같음 -> DFS로 점수를 구하고, 그 점수 보다 낮으면 탐색 X => 탐색을 최소화
- 상/하/좌/우는 for문을 돌면서 범위를 벗어난 경우를 제외해서 check하는 함수를 만들어야 함
PseudoCode
1. for문을 통해 임의의 점 선택
2. 임의의 점에서 DFS 시작
3. DFS안에서 NxN 격자를 복사 후, check 함수를 통해 같은 자동차를 제거
4. 제거된 자동차 만큼 땡겨옴 (memcopy 사용 예정)
5. 다시 임의의 점 선택 후 DFS를 통해 반복
6. Back tracking을 통해 원래 격자로 복귀
7. DFS에서 시뮬레이션 회수가 충족되면 값을 비교, 비교를 통해 최종 ans를 도출
Code
#include <stdio.h>
#include <string.h>
int N, grid[45][45], ans;
void shift(int r, int sc, int ec) {
int temp[N][3*N];
for(int i=0;i<N;i++) memcpy(temp[i], grid[i], 3*N*sizeof(int));
int len = ec - sc + 1;
for(int i = sc;i<= 3*N;i++) {
if(i+ len > 3*N) grid[r][i] = 0;
else grid[r][i] = temp[r][i+len];
}
}
int modify_grid(int r, int c) {
int color = grid[r][c];
int car_remve_num = 0;
// param
int sr = r, er = r+1;
int lsc = 46, lec = -1;
int up_flag = 1, down_flag = 1;
while(up_flag || down_flag) {
// up
if(up_flag) {
if(sr < 0 || grid[sr][c] != color) {
up_flag = 0;
sr++;
}
else {
int sc = c, ec = c+1;
int left_flag = 1, right_flag = 1;
while(left_flag || right_flag) {
if(left_flag) {
if(sc <0 || grid[sr][sc] != color) {
left_flag = 0;
sc++;
}
else {
sc--;
car_remve_num++;
}
}
if(right_flag) {
if(N-1 < ec || grid[sr][ec] != color) {
right_flag = 0;
ec--;
}
else {
ec++;
car_remve_num++;
}
}
}
shift(sr, sc,ec);
lsc = (lsc > sc) ? sc : lsc;
lec = (lec > ec) ? lec : ec;
sr--;
}
}
// down
if(down_flag) {
if(N-1 < er || grid[er][c] != color) {
down_flag = 0;
er--;
}
else {
int sc = c, ec = c+1;
int left_flag = 1, right_flag = 1;
while(left_flag || right_flag) {
if(left_flag) {
if(sc <0 || grid[sr][sc] != color) {
left_flag = 0;
sc++;
}
else {
sc--;
car_remve_num++;
}
}
if(right_flag) {
if(N-1 < ec || grid[sr][ec] != color) {
right_flag = 0;
ec--;
}
else {
ec++;
car_remve_num++;
}
}
}
shift(sr, sc,ec);
lsc = (lsc > sc) ? sc : lsc;
lec = (lec > ec) ? lec : ec;
er++;
}
}
}
return (car_remve_num +(er-sr+1)*(lec-lsc+1));
}
void DFS(int r, int c, int score, int sim_cnt) {
score += modify_grid(r,c);
if(sim_cnt == 3)
{
ans = (ans > score) ? ans : score;
return;
}
int temp[N][3*N];
for(int i=0;i<N;i++) memcpy(temp[i], grid[i], 3*N*sizeof(int));
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
DFS(i,j,score, sim_cnt+1);
// back traking
for(int i=0;i<N;i++) memcpy(grid[i], temp[i], 3*N*sizeof(int));
}
}
}
int main() {
// input data
scanf("%d", &N);
int TN = 3*N;
for(int i=0;i<TN;i++) {
for(int j=0;j<N;j++) scanf("%d", &grid[j][TN-1-i]);
}
// copy
int temp[N][3*N];
for(int i=0;i<N;i++) memcpy(temp[i], grid[i], 3*N*sizeof(int));
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++) {
DFS(i,j,0,1);
// back tracking
for(int i=0;i<N;i++) memcpy(grid[i], temp[i], 3*N*sizeof(int));
}
}
printf("%d", ans);
}
- back tracking & shift에서 문제 발생 -> 문제 해결.... 코드가 길어지니깐 엄청 햇갈림.
- Test case는 모두 맞음... 아마 시간 문제일 거 같음..
개선할 점
- 코드가 복잡할 수록 수정 하는데 어려움 => 모듈화 & 디버깅을 구현해 놓자!!
- 시간 부분에서 문제가 발생 => 현재는 완탐이기 때문에 조건을 통해서 완탐을 줄여야 함... 어떻게..?
- shift와 back tracking에서 시간 소요가 많이 되는데 이를 어떻게 해결하지...?
수정사항
- DFS & Visited를 사용해서, 이미 Check 된 부분은 건너 뜀 => 최적화(배열 복사 최소화)
- Shift 로직만 구현하면 정답일거 같음......
수정 코드
#include <stdio.h>
#include <string.h>
int N, grid[15][45], ans;
int visited[15][15];
int min_r, max_r, min_c, max_c, add;
int dir[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
void find_DFS(int r, int c, int color) {
add++;
grid[r][c] = 0;
min_r = (min_r < r) ? min_r : r;
max_r = (max_r > r) ? max_r : r;
min_c = (min_c < c) ? min_c : c;
max_c = (max_c > c) ? max_c : c;
for(int i=0;i<4;i++) {
int nr = dir[i][0], nc = dir[i][1];
if(grid[nr][nc] == 0 || grid[nr][nc] != color || visited[nr][nc]) continue;
visited[nr][nc] = 1;
find_DFS(nr,nc,color);
}
}
void garage_DFS(int cnt, int score) {
memset(visited, 0, sizeof(visited));
int temp[15][45];
memcpy(temp, grid,sizeof(grid));
for(int i=0;i<N;i++) {
for(int j=0;j<3*N;j++) {
if(grid[i][j] == 0 || visited[i][j]) continue;
memcpy(grid,temp,sizeof(grid));
int color = grid[i][j];
visited[i][j] = 1;
min_r = i, max_r = i, min_c = j, max_c = j;
add = 0;
find_DFS(i,j,color);
// shift left cars
if(cnt < 2) {
for(int r = min_r; r <= max_r; r++) {
for(int c = min_c; c <= max_c; c++) {
if(grid[r][c] != 0) continue;
int len = 0;
for(int i = c+1; i <3*N; i++) {
if(grid[r][i]) {
len = i-c;
break;
}
}
if(len) {
for(int i = c; i < c+len; i++) {
grid[r][i] = grid[r][i + len];
grid[r][i + len] = 0;
}
}
}
}
garage_DFS(cnt+1, score + add + (max_r-min_r+1)*(max_c-min_c+1));
}
else {
ans = (ans > score) ? ans : score;
continue;
}
}
}
}
int main() {
// input data
scanf("%d", &N);
int TN = 3*N;
for(int i=0;i<TN;i++) {
for(int j=0;j<N;j++) scanf("%d", &grid[j][TN-1-i]);
}
garage_DFS(0,0);
printf("%d", ans);
}
'코테...' 카테고리의 다른 글
| 백준 - 가르침(1062) 정답 (1) | 2023.12.06 |
|---|
