daily pastebin goal
63%
SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 61 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top