백준의 뿌요뿌요(11559) 문제이다.
( 문제 바로가기 )
[ 문제풀이 ]
1) 이 문제의 큰 틀부터 알아보자. 어떻게 진행해 나아가야할까??
크게 보면 이렇다.
1. 모든 좌표를 다 하나하나씩 돌아보자.
2. 돌면서, 터질 수 있는 놈들은 터트려보자.
3. 터트린 다음에는 맵을 정리해주고 반복한다.
문제의 핵심은 얼마나 연쇄로 터질 수 있냐? 가 문제이다. 몇 개의 묶음이 한번에 터질 수 있는지를 묻는 것이 아니다.
2) 구체적으로 문제를 풀면서 알아보자.
먼저 본인은 이 문제를 DFS를 통해서 구현하였다. 12 x 6 크기의 모든 좌표를 다 탐색하면서 빈공간이 아니면서
아직 한번도 탐색을 하지 않은 좌표들에 대해서 DFS를 호출해 주었다.
DFS 함수내에서의 구현 내용은 이렇다. 상하좌우를 돌면서 여러가지 조건을 만족한다면 재귀를 호출하는 방식이다.
그렇다면 고려해야할 조건에 대해서 알아보자.
1. 맵의 범위 내에 존재하는 좌표인지
2. 탐색하려는 좌표가 빈공간은 아닌지
2-1. 탐색하려는 좌표가 현재 내 뿌요와 같은 색상인지
3. 이미 탐색을 했던 좌표는 아닌지
이 3가지에 대해서 탐색해줘야한다. 이부분만 코드를 보자면 아래와 같다.
1 2 3 4 5 6 7 8 9 10 11 | for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue; // 조건1. 재범위내에 존재하는지 if (MAP[nx][ny] == '.') continue; // 조건2. 맵에서 빈공간이 아닌지 if (MAP[x][y] != MAP[nx][ny]) continue; // 조건2-1. 현재 뿌요와 같은 색상인지 if (Visit[nx][ny] == true) continue; // 조건3. 이미 탐색을 했던 좌표는 } | cs |
위의 조건문들을 모두 지나쳐서 오게 된다면 조건을 모두 만족하는 좌표라는 것이다.
그렇다면 조건을 만족했으면 구현해야 할 것을 생각해보자.
1. 탐색한 좌표라고 표시를 해줘야한다.
2. 뿌요가 4개 이상이면 터지기 때문에 뿌요의 갯수에 대해서 ++ 해줘야 한다.
3. 해당 좌표에서 DFS를 호출해줘야 한다.
지금까지의 상태에서는 위의 3가지만 만족하면 된다. 하지만, 실제 구현에서는 더 많은 것들을 해줘야 한다.
애초에 우리는 뿌요가 4개 이상이라면 터뜨릴 수 있기 때문에 뿌요의 갯수를 Count해주는 변수가 하나 필요하다.
그래서 사실, 윗부분에서 말했던, "모든좌표를 돌면서 빈공간이 아니면서 탐색을 하지 않은 좌표라면 DFS호출" 이라고
만 말을 했지만, 호출하기 전, 해당 좌표의 색깔의 뿌요를 1로 설정해줘야 한다.
또한, 뿌요가 4개 이상이라면 터트리는 작업도 필요하다. 따라서, 본인은 해당 좌표를 저장해주는 Vector를 사용하였다.
이 부분을 코드를 통해서 다시한번 정리해보자.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | for (int i = 0; i < 12; i++) { for (int j = 0; j < 6; j++) { if (MAP[i][j] != '.' && Visit[i][j] == false) // 색깔이 있는 좌표이고, 탐색하지 않은 좌표라면 ? { Temp_Cnt = 1; // 일단 뿌요의 갯수는 1개. Boom_Tmp.push_back(make_pair(i, j)); // 터질 수도 있는 뿌요이므로 Vector에 저장 Visit[i][j] = true; // 탐색했다고 표시 DFS(i, j); // DFS호출 if(Temp_Cnt >= 4) // DFS호출 이후, 뿌요가 4개 이상이라고 판단되면? { // 구현예정 } } } } | cs |
위의 코드에서 Temp_Cnt가 뿌요의 갯수를 Count하는 변수의 역할을 한다.
그렇다면, 우리는 다시 위로 올라가서 "더 많은 것"에 대해서 알아보자.
우리는 현재,
1. 제 범위 내에 있는 좌표이면서
2. 아직 탐색을 한번도 하지 않은 좌표이고
3. 현재 뿌요의 색깔과 색깔도 같은 좌표일 때
구현해야 되는 내용까지 왔다. 지금부터 이후 과정을 알아보자.
1. Temp_Cnt의 값 ++ (뿌요의 갯수를 관리하는 변수)
2. 터트려야 할 수도 있는 뿌요기 때문에 좌표를 저장 (Vector에 저장)
3. 방문했다고 표시
4. 해당 좌표에서 다시 DFS호출
위 과정을 모두 실행해줘야 하는 것이 DFS함수 안에서의 내용이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void DFS(int x, int y) { for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue; if (MAP[nx][ny] == '.') continue; if (Visit[nx][ny] == true) continue; if (MAP[x][y] != MAP[nx][ny]) continue; Temp_Cnt++; Visit[nx][ny] = true; Boom_Tmp.push_back(make_pair(nx, ny)); DFS(nx, ny); } } | cs |
지금까지 우리가 했던 일과 앞으로 남은 일들을 정리해보자.
지금까지 우리가 한 일
1. 모든 좌표를 돌면서, 터질 수 있는 가능성이 있는 뿌요들의 갯수를 Count하면서, 좌표를 저장해 두었다.
그렇다면 앞으로 남은 일들을 정리해보자.
1. 만약 뿌요의 갯수를 Count했는데 4개 이상이라면 ??
1-1) 뿌요를 터트려줘야한다.
2. 뿌요를 터트렸으면 다시 맵을 정리해주어야 한다.
3. 한번 터트렸으므로 1번 연쇄되었다고 표시해주고, 다시 위의 과정을 반복해야한다.
단계별로 해결해나가자.
1. 뿌요의 갯수가 4개 이상인 뿌요들이 존재할 경우, 터트려야 한다.
우리는 좌표를 저장해 두었기 때문에 이 부분은 어렵지 않다. Vector에 저장된 좌표들을 '.'으로만 바꿔주면 되기
때문이다. 주의해야 할 점은, 터질 수 있는 묶음들이 여러개일 경우, 그 묶음들이 한번에 터진다는 것이다.
맵이 이렇게 있을 경우, 위의 모든 A B C는 한번에 터진다는 것이다. 3묶음이 터진다고 해서 연쇄가 3번일어나는
것이 아니라는 것이다.
2. 맵을 정리하기.
맵을 정리하는 것은 어렵지 않다. 가장 아랫줄부터 위로 올라오면서 뿌요들이 존재한다면 그대로 내려주면 된다.
이런 부분은 개인의 구현 능력이 중요하다고 생각한다.
3. 사실 이 모든 과정은 while(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 119 120 121 122 123 124 125 126 127 128 129 130 131 | #include<iostream> #include<cstring> #include<queue> #include<vector> #define endl "\n" using namespace std; char MAP[12][6]; bool Visit[12][6]; int dx[] = { 0, 0, 1, -1 }; int dy[] = { 1, -1, 0, 0 }; int Boom_Cnt = 0; int Temp_Cnt = 0; vector<pair<int, int>> Boom_Tmp, Boom_Vec; void Input() { for (int i = 0; i < 12; i++) { for (int j = 0; j < 6; j++) { cin >> MAP[i][j]; } } } void DFS(int x, int y) { for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (nx < 0 || ny < 0 || nx >= 12 || ny >= 6) continue; if (MAP[nx][ny] == '.') continue; if (Visit[nx][ny] == true) continue; if (MAP[x][y] != MAP[nx][ny]) continue; Temp_Cnt++; Visit[nx][ny] = true; Boom_Tmp.push_back(make_pair(nx, ny)); DFS(nx, ny); } } void Solution() { bool Flag; int Answer = 0; while (1) { Flag = false; memset(Visit, false, sizeof(Visit)); Boom_Vec.clear(); for (int i = 0; i < 12; i++) { for (int j = 0; j < 6; j++) { if (MAP[i][j] != '.' && Visit[i][j] == false) { Temp_Cnt = 1; Boom_Tmp.push_back(make_pair(i, j)); Visit[i][j] = true; DFS(i, j); if (Temp_Cnt >= 4) { Flag = true; // 뿌요가 터졌다고 표시. for (int i = 0; i < Boom_Tmp.size(); i++) { Boom_Vec.push_back(Boom_Tmp[i]); // 해당 좌표들 옮겨주기 } } Boom_Tmp.clear(); } } } for (int i = 0; i < Boom_Vec.size(); i++) { int x = Boom_Vec[i].first; int y = Boom_Vec[i].second; MAP[x][y] = '.'; } for (int i = 10; i >= 0; i--) { for (int j = 0; j < 6; j++) { if (MAP[i][j] == '.') continue; int Tmp = i; while (1) { if (Tmp == 11 || MAP[Tmp + 1][j] != '.') break; MAP[Tmp + 1][j] = MAP[Tmp][j]; MAP[Tmp][j] = '.'; Tmp++; } } } if (Flag == true) Answer++; else break; } cout << Answer << endl; } void Solve() { Input(); Solution(); } int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("Input.txt", "r", stdin); Solve(); return 0; } | cs |
'[ BOJ Code ] > # BOJ -' 카테고리의 다른 글
| [ 백준 2225 ] 합분해 (C++) (4) | 2019.02.01 |
|---|---|
| [ 백준 15654 , 15655 ] N과M(5) , N과M(6) (C++) (0) | 2019.02.01 |
| [ 백준 6087 ] 레이저 통신 (C++) (3) | 2019.02.01 |
| [ 백준 3109 ] 빵집 (C++) (8) | 2019.01.31 |
| [ 백준 15651 , 15652 ] N과M(3) , N과M(4) (C++) (0) | 2019.01.31 |