<Dovelet> 14계단 - 댐

처음에 BFS문제인줄알고 BFS식으로 짰는데 시간초과가 나와서 당황했던 문제이다

결국엔 Queue로 풀었지만 배열이 메모리를 너무 많이 할당시켜서 깔끔해지 못했던 점이 너무 아쉬웠다

http://59.23.150.58/30stair/dam/dam.php?pname=dam

어느 마을 안에는 큰 호수가 있고, 그것을 막는 댐이 있었다. 그런데 어느날 그 댐이 무너져내려 호수에 있는 물이 마을을 모두 뒤덮으려한다. 호수에 있는 물은 다음 1시간에 한 블럭으로 이동하며, 물의 양은 무한하다 가정하자. 물은 상 하 좌 우로 퍼져나가며 마을을 뒤덮는다. 당신은 댐이 터진 순간 이 마을의 지도를 받았다. 당신이 도와줘야 할 일은 완공시간이 K시간인 댐들을 최대한 빨리 지어서 물이 더 이상 진행하지 못하도록 하는 것이다. 입력 첫 줄에는 배열의 크기인 T(1 ≤ T ≤100)가 주어지고 다음 줄부터 배열의 값이 주어진다. 0은 텅 빈 길, 1은 건물이다. (물은 건물을 뒤덮지 못한다고 가정한다.) 그리고 그 다음 줄에는 호수의 좌표 x, y가 주어지고, 다음 줄에는 댐이 지어지는 시간인 K가 주어진다. 출력 지어야 하는 댐의 숫자를 출력한다. 만약, 마을이 전부 잠길 때까지 댐을 지을 수 없거나 건물에 둘러쌓여 물이 더이상 진행을 못할 경우엔 "OH, MY GOD"을 출력한다. (좋은 의미로든, 나쁜 의미로든....)

#include<iostream> #include<stdio.h> using namespace std; struct emp { int map[105][105]; int x, y; int second,size; }; emp dam; void BFS(int sec,int y,int x) { dam.map[y][x] = 2; if (sec == 1) return; if (dam.map[y + 1][x] != 1) BFS(sec - 1, y + 1, x); if (dam.map[y - 1][x] != 1) BFS(sec - 1, y - 1, x); if (dam.map[y][x + 1] != 1) BFS(sec - 1, y, x + 1); if (dam.map[y][x - 1] != 1) BFS(sec - 1, y, x - 1); return; } int main(void) { int i, j; int dap = 0; //freopen("input.txt", "r", stdin); scanf("%d", &dam.size); for (i = 1; i <= dam.size; i++) for (j = 1; j <= dam.size; j++) scanf("%d", &dam.map[i][j]); for (i = 0; i <= dam.size + 1; i++) { dam.map[i][0] = 1; dam.map[i][dam.size + 1] = 1; dam.map[0][i] = 1; dam.map[dam.size + 1][i] = 1; } scanf("%d %d", &dam.x, &dam.y); scanf("%d", &dam.second); BFS(dam.second,dam.y,dam.x); for (i = 1; i <= dam.size; i++) { for (j = 1; j <= dam.size; j++) { if (dam.map[i][j] == 2) { if (dam.map[i + 1][j] == 0) { dam.map[i + 1][j] = 3; dap++; } if (dam.map[i - 1][j] == 0) { dam.map[i - 1][j] = 3; dap++; } if (dam.map[i][j + 1] == 0) { dam.map[i][j + 1] = 3; dap++; } if (dam.map[i][j - 1] == 0) { dam.map[i][j - 1] = 3; dap++; } } } } if (dap == 0) printf("OH, MY GOD"); else printf("%d", dap); return 0; }

이렇게 짰었는데... 시간초과나와서 멘붕이 왔었다ㅜㅜ

나중에 안 사실이지만 코드를 재귀함수로 짜면 속도가 느려진다고 했다..

정말로 울 것 같았지만,, 멘탈을 다잡고 다른방법을 연구했다

#include<stdio.h> int t, a[105][105],x,y,k; int q[1000000][3],tail,head; int x_dot,y_dot,cnt,r,dap=0; int main(void){ int i,j,k; //freopen("in.txt","r",stdin); scanf("%d",&t); for(i=0; i<=t+1; i++){ a[i][0] = 1; a[0][i] = 1; a[t+1][i] =1; a[i][t+1] = 1; } for(i=1; i<=t; i++){ for(j=1; j<=t; j++) scanf("%d",&a[i][j]); } scanf("%d %d",&x_dot,&y_dot); scanf("%d",&k); r = k; k++; q[tail][1] = x_dot; q[tail][2] = y_dot; tail++; a[y_dot][x_dot] = 2; while(tail != head){ x = q[head][1]; y = q[head][2]; head++; cnt = a[y][x]+1; if(cnt==k+1) break; ///left if(a[y][x-1]==0){ q[tail][1] = x-1; q[tail][2] = y; tail++; a[y][x-1] = cnt; } ///right if(a[y][x+1]==0){ q[tail][1] = x+1; q[tail][2] = y; tail++; a[y][x+1] = cnt; } ///up if(a[y-1][x]==0){ q[tail][1] = x; q[tail][2] = y-1; tail++; a[y-1][x] = cnt; } ///down if(a[y+1][x]==0){ q[tail][1] = x; q[tail][2] = y+1; tail++; a[y+1][x] = cnt; } } for(i=1; i<=t; i++){ for(j=1; j<=t; j++){ if(a[i][j]==0){ if((a[i][j-1]>1 && a[i][j-1]<9999) || (a[i][j+1]>1 && a[i][j+1]<9999) || (a[i+1][j]>1 && a[i+1][j]<9999) || (a[i-1][j]>1 && a[i-1][j]<9999)) a[i][j]=9999; } } } for(i=1; i<=t; i++){ for(j=1; j<=t; j++) if(a[i][j]==9999) dap++; } if(dap==0) printf("OH, MY GOD"); else printf("%d",dap); return 0; }

그래서 다시 짠코드가 이거다 변수 q가 할당한 메모리가 어마어마하다(지금 보니까 변수이름 참 대충 지은 것 같다..)

다음번엔 한번 vector를 이용해서 한번 도전해봐야겠다