[C/C++] 코드업(codeup) 2605번 캔디팡

▽문제 바로가기

https://codeup.kr/problem.php?id=2605

캔디팡

---

입력

캔디팡 격자판(7 * 7)의 색깔 정보(1~5)가 입력된다.

※ 색깔정보

빨강 = 1 , 노랑 = 2 , 파랑 = 3 , 초록 = 4 , 보라 = 5

 

출력

터치하면 터지는 영역의 개수를 출력한다.

 

문제 풀이

 

DFS/BFS 문제이긴 하나 flood fill이라는 알고리즘으로 풀 수 있다고 합니다. flood fill은 처음 알았습니다. 스택과 매우 유사하다는 느낌을 받았습니다.

 

행, 열, 색깔을 매개변수로 넘겨주고 일치하면 그 위치의 색깔정보를 전혀 상관없는 0으로 만들어서 재탐색을 방지할 수 있습니다.

 

#include <stdio.h>

using namespace std;
int arr[7][7];

int candy(int row, int col, int color){
	//범위밖이면 리턴
	if(row==-1||col==-1||row==7||col==7) return 0;
	
	//같은색이 아니면 리턴 
	if(arr[row][col]!=color) return 0;
	
	//같은색이면 0으로 만듬
	if(arr[row][col]==color) arr[row][col] = 0;
	
	//상, 하, 좌, 우 로 탐색
	return 1+candy(row-1, col, color)+candy(row+1, col, color)+candy(row, col-1, color)+candy(row, col+1, color);
}

int main(){
	
	for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			scanf("%d", &arr[i][j]);
		}
	}
	
	int cnt = 0;
	for(int i=0;i<7;i++){
		for(int j=0;j<7;j++){
			int temp = 0; 
			if(arr[i][j]!=0){
				temp = candy(i, j, arr[i][j]);
			}
			if(temp>=3) cnt++;
		}
	}
	
	printf("%d", cnt);
	
}