[C/C++] 코드업(codeup) 4060번 전광판 전구 조작

▽문제 바로가기

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

전광판 전구 조작

---

입력

첫째 줄에 전광판의 크기를 나타내는 세로 길이 M과 가로 길이 N이 입력된다. (2<=M,N<=100인 자연수)

둘째줄 부터 M줄에 걸쳐 N열 만큼의 전구들의 상태가 주어진다. 이때 켜진 상태는 1, 꺼진 상태는 0으로 입력된다.

 

출력

모든 전구를 켜기 위한 최소 조작횟수와 모두 끄기 위한 최소조작횟수를 각각 공백으로 구분하여 출력하라.

 

문제 풀이

 

 

이 문제는 코드업 2610번 그림판 채우기 문제와 매우 유사합니다.

 

▽ 코드업 2610번 그림판 채우기 바로가기

https://swblossom.tistory.com/83

[C/C++] 코드업(codeup) 2610번 그림판 채우기

 

동서남북으로 이웃한 전구를 탐색하면 됩니다.

 

#include <stdio.h>

using namespace std;

int m, n;
int arr1[101][101];	//모두 켜는거 계산용 
int arr2[101][101];	//모두 끄는거 계산용
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

//전구를 켜는 함수
void recur1(int row, int col){
	if(row==-1||col==-1||row==m||col==n) return;
	
	if(arr1[row][col]==1) return;
	
	arr1[row][col] = 1;
	for(int i=0;i<4;i++) recur1(row+dy[i], col+dx[i]);
	
}

//전구를 끄는 함수
void recur2(int row, int col){
	if(row==-1||col==-1||row==m||col==n) return;
	
	if(arr2[row][col]==0) return;
	
	arr2[row][col] = 0;
	for(int i=0;i<4;i++) recur2(row+dy[i], col+dx[i]);
	
}

int main(){
	
	scanf("%d%d", &m, &n);
	
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			scanf("%d", &arr1[i][j]);
			arr2[i][j] = arr1[i][j];
		}
	}
	
	int cnt1 = 0, cnt2 = 0;
	for(int i=0;i<m;i++){
		for(int j=0;j<n;j++){
			if(arr1[i][j]==0) {recur1(i, j); cnt1++;}	//전구꺼져있다면 켜기
			if(arr2[i][j]==1) {recur2(i, j); cnt2++;}	//전구켜져있다면 끄기
		}
	}
	
	printf("%d %d", cnt1, cnt2);
	
	return 0;
}