[코드업] 2605 : 캔디팡 (C)

알고리즘

Flood Fill

풀이

문제 그대로 같은 색으로 이어진 칸들의 갯수를 세면 된다.

배열 범위를 벗어나는지 좀 더 편리하게 체크하기위해서 배열의 크기를 9*9로 잡아 주었다.

입력값에 0이 없기 때문에 in[i][j]가 0이라면 배열의 범위를 벗어난 것으로 확인할 수 있다.

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

#include<iostream> using namespace std;   int in[9][9]; int check[8][8];    // 한번 방문했던 곳 체크  int dir[4][2]={{1,0}, {0,1}, {-1,0}, {0,-1}};    // 방향배열    int ans;   int search(int a,int b){  //flood fill 재귀 구현        check[a][b]=1;     int cnt=1;     for(int i=0;i<4;i++){         int na=a+dir[i][0], nb=b+dir[i][1];                  if(check[na][nb]||!in[na][nb])             continue;                  if(in[na][nb]==in[a][b])             cnt+=search(na,nb);     }          return cnt; }   int main(){     for(int i=1;i<=7;i++){         for(int j=1;j<=7;j++){             cin>>in[i][j];         }     }       for(int i=1;i<=7;i++){         for(int j=1;j<=7;j++){             if(search(i,j)>=3)                 ans++;         }     }          cout<<ans; }