Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 8.11 KB | None | 0 0
  1. // Baaaaaaaaaduk2 (Easy)
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <stdbool.h>
  6.  
  7. int arr[21][21] = {0,}; // 처음 입력받은 Map 배열(바둑판)
  8. int cal[21][21] = {0,}; // 따로 착수를 하려는 Map 배열(바둑판)
  9. bool queCheck[21][21] = {false,}; // DFS로 지금 위치의 흑돌이 살아있는 흑돌인지 죽어있는 흑돌인지 판단할 때 사용할 배열
  10. bool Catch[21][21] = {false,}; // 기본적으로 false로 초기화하고 흑돌 위치인데 false면 살아있는 흑돌, true면 죽은 흑돌, 우리가 점수로 계산할 흑돌이라는 뜻
  11. int dir_x[4] = {-1, 0, 1, 0}; // 상, 하, 좌, 우 계산하려고 만듬.
  12. int dir_y[4] = {0, 1, 0, -1};
  13.  
  14. bool check(int x, int y, int N, int M){ // 해당 포지션이 바운더리를 넘어갔는지 안 넘어 갔는지 체크하는 함수
  15. if( x<0 || y<0 || x>=N || y>=M ){
  16. return false;
  17. }else{
  18. return true;
  19. }
  20. }
  21.  
  22. void Dfs(int x, int y, int N, int M){ // 해당 흑돌이 살아있는지 안 살아있는지 인접한 모든 흑돌의 상태를 체크해보고 지금 자신의 흑돌의 상태를 판별할 수 있다.
  23. // 해당 그룹에 단 하나의 흑돌이라도 살아있으면 그 그룹 전체의 흑돌은 살아있다.
  24. int i;
  25. int dx, dy;
  26. bool flag = false;
  27.  
  28. queCheck[x][y] = true; // DFS할때 visited[v]하는 배열처럼
  29. for(i=0;i<4;i++){
  30. dx = x+dir_x[i];
  31. dy = y+dir_y[i];
  32. if(check(dx, dy, N, M)){ // 해당 좌표가 바둑판을 벗어나지 않으면서,
  33. // 지금 이 흑돌과 상,하,좌,우로 연결된 어떠한 흑돌이라도 살아있으면 나머지 방향은 검사할 필요도 없음. 살아있음이 보장됐기 때문에.
  34. if(cal[dx][dy] == 2 && Catch[dx][dy] == false && queCheck[dx][dy] == false){
  35. flag = true;
  36. break;
  37. }else;
  38. }else;
  39. }
  40.  
  41. if(flag == true){ // 이 돌은 살아있음.
  42. Catch[x][y] = false;
  43. return ;
  44. }
  45.  
  46. for(i=0;i<4;i++){ // 지금 이 돌이 죽었는지 살았는지 정확하게 몰라 == 빈 공간과 인접하진 않고 흑돌과 인접한 경우, 인접한 흑돌도 검사해야댐.
  47. dx = x+dir_x[i];
  48. dy = y+dir_y[i];
  49. if(check(dx, dy, N, M)){ // 바둑판 좌표 내에 존재하고, 인접한 흑돌이고, 그 인접한 흑돌이 아직 검사하지 않은 상태면 검사.
  50. if(cal[dx][dy] == 2 && Catch[dx][dy] == true && queCheck[dx][dy] == false){
  51. Dfs(dx, dy, N, M);
  52. }else;
  53. }else;
  54. }
  55. }
  56.  
  57. int main()
  58. {
  59. bool flag = true;
  60. int N, M;
  61. int i, j, k, l, m;
  62. int dx, dy;
  63. int cnt = 0; // 검색할 좌표가 몇 개인지
  64. int sum = 0; // 착수한 Case마다 잡을 수 있던 흑돌의 최대 개수
  65. int max = 0; // 정답
  66. int pos[2][1601] = {0,}; // 런타임에러가 발생했던 이유, 우리가 착수할 수 있는 모든 좌표를 여기에 담으려고 했는데 구하는 과정에서 중복이 포함되게 설정해놨다. 그래서 401개에서 커버가 되는 것이 아니라 1601개 까지 할당했음.
  67.  
  68. // 초기화
  69. for(i=0;i<20;i++){
  70. for(j=0;j<20;j++){
  71. arr[i][j] = 0;
  72. cal[i][j] = 0;
  73. Catch[i][j] = false;
  74. queCheck[i][j] = false;
  75. }
  76. }
  77.  
  78. for(i=0;i<2;i++){
  79. for(j=0;j<1601;j++){ // 정답 제출했을땐 401로 해서 통과됐으나 정확히는 1601로 바꿔줘야 쓰레기값을 대비할 수 있음.
  80. pos[i][j] = 0;
  81. }
  82. }
  83.  
  84. scanf("%d %d", &N, &M);
  85. for(i=0;i<N;i++){
  86. for(j=0;j<M;j++){
  87. scanf("%d", &arr[i][j]);
  88. cal[i][j] = arr[i][j];
  89. }
  90. }
  91.  
  92. dx = 0;
  93. dy = 0;
  94. for(i=0;i<N;i++){
  95. for(j=0;j<M;j++){
  96. if(arr[i][j] == 2){ // 바둑판에서 흑돌을 찾았음.
  97. for(k=0;k<4;k++){
  98. dx = i+dir_x[k];
  99. dy = j+dir_y[k];
  100. if(check(dx, dy, N, M)){
  101. if(arr[dx][dy] == 0){ // 그 흑돌과 상, 하, 좌, 우로 인접한 빈 공간(0)을 찾음 == 우리가 착수할 가능성이 있는 공간
  102. pos[0][cnt] = dx; // 같은 좌표가 상,하,좌,우에 검사하면서 최대 4번까지 중복될 수 있기 때문에, 3번문제가 1000X1000사이즈 바둑판이니까 중복처리를 해줘야 될 듯.
  103. pos[1][cnt] = dy;
  104. cnt++;
  105. }else;
  106. }else;
  107. }
  108. }
  109. }
  110. }
  111. dx = dy = 0;
  112. for(i=0;i<cnt-1;i++){
  113. for(j=i+1;j<cnt;j++){
  114. cal[pos[0][i]][pos[1][i]] = 1; // 가능한 좌표에 돌 하나를 착수함.
  115. cal[pos[0][j]][pos[1][j]] = 1; // 가능한 좌표에 돌 하나를 착수함.
  116. for(k=0;k<N;k++){
  117. for(l=0;l<M;l++){
  118. if(cal[k][l] == 2){ // 흑돌을 발견했다.
  119. flag = true;
  120. for(m=0;m<4;m++){
  121. dx = k+dir_x[m];
  122. dy = l+dir_y[m];
  123. if(check(dx, dy, N, M)){
  124. if(cal[dx][dy] == 0){ // 그 흑돌 근처에 빈 공간이 있다 == 그 흑돌은 살았다. == 다른 좌표 검사할 필요없이 이 흑돌은 살아있음이 보장됀다.
  125. flag = false;
  126. }else;
  127.  
  128. }else;
  129. if(!flag){
  130. Catch[k][l] = false; // 이 흑돌은 살아있다. 잡아먹을 수 없는 흑돌이다.
  131. break;
  132. }
  133. }
  134. if(flag){ // 상,하,좌,우를 다 검사해봤는데 인접한 빈 공간이 없다. 이 흑돌은 죽어있다. 먹을 수 있는 흑돌이다.
  135. Catch[k][l] = true;
  136. }
  137. }
  138. }
  139. }
  140.  
  141. // 초기화
  142. for(k=0;k<N;k++){
  143. for(l=0;l<M;l++){
  144. queCheck[k][l] = false;
  145. }
  146. }
  147.  
  148. flag = true;
  149. for(k=0;k<N;k++){
  150. for(l=0;l<M;l++){
  151. if(Catch[k][l] == true && cal[k][l] == 2){ // 위에서 1차적으로 검사했을 땐 인접한 상,하,좌,우가 빈 공간이 있냐, 없냐를 기준으로 살아있냐 죽어있냐를 판단했음.
  152. Dfs(k, l, N, M); // 위에선 인접한 돌이 흑돌인 경우에 그 흑돌이 살아있는지 죽어있는지에 따라 이 돌이 살아있냐 죽어있냐를 알 수 있는데, 인접한 모든 흑돌을 검사해야 하기 때문에 DFS사용
  153. for(m=0;m<4;m++){ // DFS 끝나고 맨 처음 DFS 호출했던 그 위치도 최신화를 해줘야 되서 한 번 더 돌려줌 -> 구현문제임
  154. dx = k+dir_x[m];
  155. dy = l+dir_y[m];
  156. if(check(dx, dy, N, M)){
  157. if(cal[dx][dy] == 2 && Catch[dx][dy] == false){
  158. flag = false;
  159. }else;
  160. }else;
  161. }
  162. if(flag == false){
  163. Catch[k][l] = false;
  164. }
  165. }
  166. flag = true;
  167. }
  168. }
  169.  
  170. sum = 0;
  171. for(k=0;k<N;k++){
  172. for(l=0;l<M;l++){
  173. if(Catch[k][l] == true){ // 잡아 먹을 수 있는 돌의 개수 계산
  174. sum++;
  175. }
  176. }
  177. }
  178.  
  179. // 초기화
  180. for(k=0;k<N;k++){
  181. for(l=0;l<M;l++){
  182. Catch[k][l] = false;
  183. queCheck[k][l] = false;
  184. }
  185. }
  186. max = max>sum?max:sum;
  187. sum = 0;
  188. cal[pos[0][i]][pos[1][i]] = 0;
  189. cal[pos[0][j]][pos[1][j]] = 0;
  190. }
  191. }
  192. printf("%d", max);
  193. return 0;
  194. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement