Difference between r1.2 and the current
@@ -8,15 +8,133 @@
= 코드 =
== 15이원준 ==
{{{
#include<iostream>
using namespace std;
int arr[100][100] = {0,};
int visit[100][100] = {0,};
int X, Y, cNum = 0;
int N, ans = 0;
void check(int x, int y, int H){
if(x <0 || y < 0 || x > X-1 || y > Y-1 || visit[x][y] == H){
return;
}
visit[x][y] = H;
if(arr[x][y] == 1){
cNum--;
arr[x][y] = H;
return;
}
check(x+1,y, H);
check(x,y+1, H);
check(x-1,y, H);
check(x,y-1, H);
}
int main(){
cin>> X >> Y;
for(int i = 0; i<X; i++){
for(int j = 0; j<Y; j++){
int tmp;
scanf("%d", &tmp);
if(tmp == 1){
cNum++;
}
arr[i][j] = tmp;
}
}
int H = 1;
while(cNum){
H++;
ans = cNum;
check(0,0,H);
}
cout<< H -1 << endl << ans<< endl;
}
}}}
== 박인서 =={{{
#include <iostream>
int c[102][102];
bool visit[102][102];
int n, m;
void change(int x, int y) {
visit[x][y] = true;
//이웃한 곳으로 이동
if (x > 0 && c[x - 1][y] == 0 && !visit[x - 1][y])
change(x - 1, y);
if (y > 0 && c[x][y - 1] == 0 && !visit[x][y - 1])
change(x, y - 1);
if (x <= n && c[x + 1][y] == 0 && !visit[x + 1][y])
change(x + 1, y);
if (y <= m && c[x][y + 1] == 0 && !visit[x][y + 1])
change(x, y + 1);
//치즈가 녹는지 체크
if (c[x - 1][y] == 1) c[x - 1][y]++;
if (c[x][y - 1] == 1) c[x][y - 1]++;
if (c[x + 1][y] == 1) c[x + 1][y]++;
if (c[x][y + 1] == 1) c[x][y + 1]++;
}
int cheese() {
change(0, 0);
int res = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
switch (c[i][j]) {
case 1:
res++;
break;
default:
c[i][j] = 0;
break;
}
}
}
return res;
}
int main()
{
std::cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++)
std::cin >> c[i][j];
}
int res = 0;
for (int t = 1;; t++) {
for (int i = 0; i <= n + 1; i++) {
for (int j = 0; j <= m + 1; j++)
visit[i][j] = false;
}
int pres = cheese();
if (pres == 0) {
std::cout << t << std::endl << res;
break;
}
else res = pres;
}
return 0;
}
}}}== 곽정흠 ==
= 아이디어 =
== 15이원준 ==
* arr은 치즈 상태표시, visit은 들른곳 체크, cNum 남은치즈 갯수
* arr[i][j]의 의미: 0이면 아무것도 없는 곳, 1이면 치즈가 있는곳, H이면 H-2시간일 때 치즈가 없어졌음.
* 각 시간마다 0,0을 출발로 dfs방식으로 네방향을 arr을 검사합니다. 만약 1을 만난다면 cNum--하고 arr을 H로 바꾸고 찾는것을 멈춥니다.
* cNum으로 치즈가 남아있는지 검사
* cNum을 ans에 저장하고 탐색을 하다가 0이 되면 H-2와 ans를 출력
== 박인서 ==
* (0,0)을 기준으로 이웃에 0인 점을 다 찾아낸다.
3.1. 15이원준 ¶
#include<iostream> using namespace std; int arr[100][100] = {0,}; int visit[100][100] = {0,}; int X, Y, cNum = 0; int N, ans = 0; void check(int x, int y, int H){ if(x <0 || y < 0 || x > X-1 || y > Y-1 || visit[x][y] == H){ return; } visit[x][y] = H; if(arr[x][y] == 1){ cNum--; arr[x][y] = H; return; } check(x+1,y, H); check(x,y+1, H); check(x-1,y, H); check(x,y-1, H); } int main(){ cin>> X >> Y; for(int i = 0; i<X; i++){ for(int j = 0; j<Y; j++){ int tmp; scanf("%d", &tmp); if(tmp == 1){ cNum++; } arr[i][j] = tmp; } } int H = 1; while(cNum){ H++; ans = cNum; check(0,0,H); } cout<< H -1 << endl << ans<< endl; }
3.2. 박인서 ¶
#include <iostream> int c[102][102]; bool visit[102][102]; int n, m; void change(int x, int y) { visit[x][y] = true; //이웃한 곳으로 이동 if (x > 0 && c[x - 1][y] == 0 && !visit[x - 1][y]) change(x - 1, y); if (y > 0 && c[x][y - 1] == 0 && !visit[x][y - 1]) change(x, y - 1); if (x <= n && c[x + 1][y] == 0 && !visit[x + 1][y]) change(x + 1, y); if (y <= m && c[x][y + 1] == 0 && !visit[x][y + 1]) change(x, y + 1); //치즈가 녹는지 체크 if (c[x - 1][y] == 1) c[x - 1][y]++; if (c[x][y - 1] == 1) c[x][y - 1]++; if (c[x + 1][y] == 1) c[x + 1][y]++; if (c[x][y + 1] == 1) c[x][y + 1]++; } int cheese() { change(0, 0); int res = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { switch (c[i][j]) { case 1: res++; break; default: c[i][j] = 0; break; } } } return res; } int main() { std::cin >> n >> m; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) std::cin >> c[i][j]; } int res = 0; for (int t = 1;; t++) { for (int i = 0; i <= n + 1; i++) { for (int j = 0; j <= m + 1; j++) visit[i][j] = false; } int pres = cheese(); if (pres == 0) { std::cout << t << std::endl << res; break; } else res = pres; } return 0; }