[Algorithm][DFS][정올] 1840 : 치즈

순서

I. 문제

II. 접근

III. 구현

문제출처 : jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1113&sca=3030

 

---

I. 문제

너무 길어서 캡쳐...

 

요약>> 배열의 치즈 모양이 주어지는데, 공기(0)과 접촉되면 1 시간 뒤 사라진다.
내부가 비어있긴 하지만 공기는 없어서 다른 부분이 사라지며 공기가 유입되어야 한다.
모두 녹는데 걸리는 시간과 모두 녹기 한 시간 전에 남은 치즈조각의 칸 개수는?

 

입력형식 첫째 줄에는 사각형 모양 판의 세로와 가로 길이가 주어진다. (양의 정수로 최대 100) 둘째 줄부터 각 가로줄의 모양이 차례로 주어진다. (각 가로줄의 모양은 공백으로 구분된다) 치즈가 없는 칸은 0, 있는 칸은 1로 주어진다.	출력형식 첫째 줄에는 치즈가 모두 녹아서 없어지는데 걸리는 시간 둘째 줄에는 그 한 시간 전 남아있는 치즈 조각의 칸 수
13 12 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0	3 5

 

---

II. 접근 (DFS - FloodFill)

1. 입력

2중 for문으로 scanf하면된다.

 

2. 문제 풀이

앞서 나왔던 문제인 "둘레 길이 구하기"와 비슷하다.

차이점은 DFS과정을 치즈가 다 사라질 때 까지 반복하는 것 이다.

바깥 0인 지점부터 DFS를 쭉 돌면 겉부분을 다 탐색하게 되는데,
0인 지점에서 4방향을 탐색해 1이 보이면 0으로 바꾸어 준다.
(치즈가 녹는 것)

바깥 0에서 시작해야, 내부가 연결되면 DFS로 접근 가능하고,
치즈로 막혀있다면 내부는 무시하게 된다.

중요!! 이때, 0으로 바꾸면 다른 부분에서 0을 보고 확산해 들어올 수 있으므로
Visit배열도 추가로 방문표시해서 중복을 막아줘야 한다.

그렇게 한번 쭉 돌아서 치즈를 삭제하면 1단계가 완료되고 이를 반복한다.

 

3. 출력

걸리는 시간은, 매 단계마다 Time++해주면 된다.

문제는 끝나기 전에 남은 치즈 수인데,

치즈의 총 개수를 구해두고 매 DFS 확산마다 --해준다.

총 개수가 0이 되면, 그 전의 치즈 개수를 출력
(새로운 변수에 매 단계마다 백업을 해두면 된다.)

 

III. 구현

<hide/>
#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

int col, row;
int map[100 + 10][100 + 10]; // 주 배열
int visit[100 + 10][100 + 10]; //방문배열

int cheesecnt{ 0 }; //전체 치즈개수
int lastcnt{ 0 }; // 백업해둘 변수

void input() {
	cin >> col >> row;
	for (int i = 0; i < col; i++) {
		for (int j = 0; j < row; j++) {
			cin >> map[i][j];
			// map에 넣어주며 치즈 총 개수 카운트
			if (map[i][j]) cheesecnt++;
		}
	}
}

void DFS(int i, int j) {

	int dx[4] = { 0,0,-1,1 };
	int dy[4] = { 1,-1,0,0 };


	// 치즈발견
	if (map[i][j] == 1) {
		cheesecnt--;
		map[i][j] = 0; // 치즈 없애줌
		visit[i][j] = 1; // 방문처리
		return;
	}


	// 치즈가 아니면서 + 방문을 안했다면

	else if (!visit[i][j]) {
		visit[i][j] = 1; //방문처리
        
		//4방향 탐색
		for (int ii = 0; ii < 4; ii++) {

			int nexty = i + dy[ii];
			int nextx = j + dx[ii];

			// 바깥으로 나가면 무시
			if (nexty == -1 or nextx == -1
				or nexty == col or nextx == row) continue;

			// 확산
			DFS(nexty, nextx);
		}
	}
	return;
}


int main() {

	memset(map, 0, sizeof(map));
	input();
    
	int time{ 0 };
    
	//치즈 총 개수가 0될 때까지 단계 반복
	while (cheesecnt != 0) {

		// 방문 배열은 매 단계마다 초기화 해줘야함.
		memset(visit, 0, sizeof(visit));

		// 가장 최근에 남은 갯수로 백업시켜놓음.
		lastcnt = cheesecnt;
        
		// DFS 시작
		// 가장 가장자리는 치즈가 없으니 (0,0)은 무조건 공기
		DFS(0, 0);
        
		time++; // 시간늘려줌

	}

	cout << time << endl;
	cout << lastcnt << endl;

	return 0;
}

 

구현 자체는 DFS를 반복 하는 것으로 , 그리고 방문표시가 중요한 문제였다.

방문표시를 하지 않게 되면 같은 단계에서 치즈를 더 파고들어갈 수 있다.

다 사라지기 전 개수를 알아내는 방법도 고민이 필요한 문제였다.

(처음에는 벡터로 별짓 다 했다...)