[C++]2636_치즈

치즈

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

17997

9586

6964

52.918%

 

 

문제

 

아래 <그림 1>과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(<그림 1>에서 네모 칸에 X친 부분)에는 치즈가 놓여 있지 않으며 치즈에는 하나 이상의 구멍이 있을 수 있다.

이 치즈를 공기 중에 놓으면 녹게 되는데 공기와 접촉된 칸은 한 시간이 지나면 녹아 없어진다. 치즈의 구멍 속에는 공기가 없지만 구멍을 둘러싼 치즈가 녹아서 구멍이 열리면 구멍 속으로 공기가 들어가게 된다. <그림 1>의 경우, 치즈의 구멍을 둘러싼 치즈는 녹지 않고 ‘c’로 표시된 부분만 한 시간 후에 녹아 없어져서 <그림 2>와 같이 된다.

<그림 1> 원래 치즈 모양

다시 한 시간 후에는 <그림 2>에서 ‘c’로 표시된 부분이 녹아 없어져서 <그림 3>과 같이 된다.

<그림 2> 한 시간 후의 치즈 모양

<그림 3> 두 시간 후의 치즈 모양

<그림 3>은 원래 치즈의 두 시간 후 모양을 나타내고 있으며, 남은 조각들은 한 시간이 더 지나면 모두 녹아 없어진다. 그러므로 처음 치즈가 모두 녹아 없어지는 데는 세 시간이 걸린다. <그림 3>과 같이 치즈가 녹는 과정에서 여러 조각으로 나누어 질 수도 있다.

입력으로 사각형 모양의 판의 크기와 한 조각의 치즈가 판 위에 주어졌을 때, 공기 중에서 치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다

. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 치즈가 없는 칸은 0, 치즈가 있는 칸은 1로 주어지며 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력하고, 둘째 줄에는 모두 녹기 한 시간 전에 남아있는 치즈조각이 놓여 있는 칸의 개수를 출력한다.

예제 입력 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

예제 출력 1 복사

3
5

---

풀이

 

Dfs를 사용해서 0일때는 계속 dfs 진행, 1일때는 dfs 탈출을 하여 치즈 겉면에만 접근할 수 있다.

첫 한시간 동안 치즈 겉면이 녹을 때  dfs로 접근은 어떤 순서로 이루어지는지 표시해봤다.

진행 중간에 순서가 헷갈릴 듯해서 빨간색 펜에서 파란색으로 바꿨다.

 

아래 데이터는 인덱스 접근 순서마다 y x를 찍은 것이다.

0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 11 2 11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 11 11 11 12 11 12 10 11 10 10 10 9 10 8 10 7 10 6 10 5 10 4 10 3 10 2 10 1 10 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 9 10 9 11 9 12 9 12 8 11 8 12 7 11 7 12 6 11 6 12 5 11 5 12 4 11 4 12 3 11 3 12 2 11 2 12 1 11 1 10 1 9 1 8 1 7 1 6 1 7 2 7 0 6 0 5 0 4 0 3 0 2 0 1 0 0 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 2 8 2 7 2 6 3 6 3 7 4 6 3 5 2 5 2 4 3 4 4 4 3 3 2 3 2 2 3 2 2 1 3 1 4 5 4 1 5 1 8 0 9 0 10 0 11 0 12 0 8 2 9 2 10 2 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 4 7 5 7

 

0,0에서 시작해서 dfs를 하는 이유는 0과 인접해있는 1에 접근하기 위해,

즉 (0,0)에서 dfs를 하면 치즈 겉면에만 접근할 수 있다.

0이면 진행하고 1이면 더 이상 진행하지 않으므로써 가능하다.

 

소스코드

#include<bits/stdc++.h>
using namespace std;
int a[104][104], visited[104][104];
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1}; 

int n,m,cnt,cnt2;
vector <pair<int,int>>v;

void input(){
	cin >> n >> m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++)
			cin >> a[i][j];
	}
}
void dfs(int y,int x){
	if(a[y][x]==1){
		v.push_back({y,x});
		return;
	}
	for(int i=0;i<4;i++){
		int ny=y+dy[i];
		int nx=x+dx[i];
		if(ny<0 || ny>=n || nx<0 || nx>=m || visited[ny][nx])
			continue;
		visited[ny][nx]=1;
		dfs(ny,nx);
	}
}

int main(void){
	input();
	cnt=0;//치즈가 녹는데 걸리는 시간 
	while(1){
		cnt2=0;//치즈가 다 녹기 한시간 전 치즈 조각 개수 
		memset(visited,0,sizeof(visited));
		v.clear(); 
        
        //치즈 겉면 벡터에 저장하기 위해 dfs
		dfs(0,0);
		for(pair<int, int> b : v)if(a[b.first][b.second] == 1)cnt2++; //치즈가 완전 소멸하기 한시간 전에 몇 조각이 남아있는지 
        for(pair<int, int> b : v)a[b.first][b.second] = 0; //치즈 겉면을 녹은 것으로 변경한다. 

        cnt++;//치즈가 녹는데 걸리는 시간 카운트 
        bool flag = 0; //치즈가 다 녹았는지 확인 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(a[i][j] != 0) flag = 1; // 치즈 조각이 있음 
            }
        }
        if(!flag) break;
    }
    cout<<cnt<<"\n"; //치즈가 다 녹는 데 걸린 시간 
    cout<<cnt2<<"\n"; //치즈가 다 녹기 한시간 전 치즈조각 개수 	
	return 0;
}

 

---

Review

*

치즈 겉면만 녹이는 코드를 어떻게 작성해야 될지 몰랐다.

dfs 진행 과정을 잘 이해하고 있었다면 문제 푸는 법을 바로 알았을 것 같다.

그래도 조금은 안다고 생각했던 dfs였지만 공부는 항상 부족한 것 같다.