https://www.acmicpc.net/problem/11559
풀이
1. 같은 문자가 4개 이상으로 뭉쳐져 있는 곳들을 BFS를 통해 찾아 없앤다.
없을경우 탐색을 종료.
-> 처음에 DFS로 찾았는데 ㅗ 모양은 제거 못 하더라..ㅎㅎ생각해보면 당연함. 내가 잘못 생각하는 것 일수도 있고.
2. 연쇄 ++;
3. 중력으로 문자들이 아래로 떨어진다~~~
4. 1로 다시 돌아간다.
여기서 중요한건!!!!!!!!!!!!!!!!
중력으로 문자들이 떨어질 때 문자들을 없애는 동작이 1회라는 거나..나는 예로 4개 이상의 R을 없애고 +1, Y를 없애고 +1을 하였는데,
이렇게 하는게 아니라 R, Y를 모두 없앤 후 +1이다.
제출한 코드
(코드상에 약간 이상한 부분이 있으나..왜 그런지 몰라 고민중이다. 그래도 정답이니깐 일단 올린다. 만약 내가 처음에 생각한데로 R없애고 +1, Y없애고 +1 이런 식이면 틀릴 것 이다.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 | #include <stdio.h> #include <string.h> char map[14][10]; int map_check[14][10]; int Q_y[1000], Q_x[1000], Q_front = -1, Q_back = -1; int dx[] = { 1,-1,0,0 }, dy[] = { 0,0,1,-1 }; int answer; //////////////////////////////////////////////////////////////////////////// void gravity(int y, int x, char CH)//문자를 내린다 { map[y][x] = '.'; while (1) { y++; if (y == 12 || map[y][x] != '.') break; } map[y - 1][x] = CH; } void search_2()//내려야될 문자를 찾는다 { for (int i = 0; i < 6; i++) { for (int j = 11; j >= 0; j--) { if (map[j][i] != '.') gravity(j, i, map[j][i]); } } } /////////////////////////////////////////////////////////////////////////// int fc(int y, int x, char CH)//4개 이상이면 지워요~ { int num = 1; int flag = 0; memset(Q_x, 0, sizeof(Q_x)); memset(Q_y, 0, sizeof(Q_y)); memset(map_check, 0, sizeof(map_check)); Q_front = Q_back = -1; Q_x[++Q_back] = x; Q_y[Q_back] = y; while (Q_front != Q_back) { int xx = Q_x[++Q_front]; int yy = Q_y[Q_front]; map_check[yy][xx] = 1; for (int i = 0; i < 4; i++) { int xxx = xx + dx[i]; int yyy = yy + dy[i]; if (xxx < 0 || yyy < 0 || xxx>5 || yyy>12 || map_check[yyy][xxx]) continue; if (map[yyy][xxx] == CH) { Q_x[++Q_back] = xxx; Q_y[Q_back] = yyy; num++; } } } //printf("/////////// %d / %d %d \n",Q_back, Q_y[0],Q_x[0]); if (num >= 4) { for (int i = 0; i <= Q_back; i++) { map[Q_y[i]][Q_x[i]] = '.'; } flag = 1; } return flag; } int search()//뒤져뒤져~ { int flag = 0, F = 0; for (int i = 11; i >= 0; i--) { for (int j = 0; j < 6; j++) { if (map[i][j] != '.') { flag += fc(i, j, map[i][j]); } } } if (flag) answer++; return flag; } int main() { int temp = 0; for (int i = 0; i < 12; i++) scanf("%s", map[i]); search(); search_2(); while (temp<12*6) { search(); search_2(); temp++; } printf("%d\n", answer); return 0; } | cs |
'SW 업무 관련 > 백준' 카테고리의 다른 글
[BEAKJOON] 2456_나는 학급회장이다_C언어 (0) | 2017.09.10 |
---|---|
[BEAKJOON] 2146_다리 만들기_C언어 (0) | 2017.09.08 |
[BEAKJOON] 1251_단어 나누기_C언어 (0) | 2017.09.08 |
[BEAKJOON] 4948_베르트랑 공준_C언어 (0) | 2017.09.03 |
[BEAKJOON] 1063_킹_C언어 (0) | 2017.09.03 |