SHARE
TWEET

Untitled

a guest Mar 23rd, 2019 63 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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top