1R/2016 09 22

오늘의 문제

• [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;
}

박인서

#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인 점을 다 찾아낸다.
• 그 0인 점 중 이웃이 1인 점의 값을 2로 바꿈.
• 그 2인 점의 값을 0으로 바꿈.
• 계속 반복한다.