#include #include #include /* * 2024403072 소프트웨어학부 이대원 * * 사고 과정 * * 치즈가 녹는 것을 시뮬레이션하는 문제 * 외부 공기와 몇 개의 면이 맞닿아있는지 판별하는 로직이 필요하다 * 3가지 과정으로 나눈다. * 1. 외부 공기인지 내부 공기인지 판별 * 2. 외부 공기와 몇 개의 면이 맞닿아있는지 판별 * 3. 상태 갱신 * * 1. 외부 공기인지 내부 공기인지 판별 (Flood fill) * BFS 또는 DFS를 통해 (0,0)과 연결된 부분을 외부 공기로 판단하면 된다. O(NM)의 시간복잡도를 가질 것이다. * * 2. 외부 공기와 몇 개의 면이 맞닿아있는지 판별 * 위 flood fill을 하는 과정에서 외부 공기와 치즈가 맞닿은 횟수를 기록 후, 일정 값 이상이 되면 다음 상태에서 치즈 제거 * * 3. 상태 갱신 */ int N, M; char grid[2][100][100]; int cheese_num = 0; void getInput() { scanf("%d %d", &N, &M); (void)getchar(); for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { grid[0][r][c] = getchar(); if (grid[0][r][c] == '1') cheese_num++; (void)getchar(); } } memcpy(grid[1], grid[0], 100 * 100); } int isInvalid(int r, int c) { return r < 0 || c < 0 || r >= N || c >= M; } void DFS(int time, int r, int c) { const int dr[4] = { -1, 1, 0, 0 }; const int dc[4] = { 0, 0, -1, 1 }; grid[time % 2][r][c] = '.'; // visited for (int i = 0; i < 4; i++) { int next_r = r + dr[i]; int next_c = c + dc[i]; if (isInvalid(next_r, next_c)) continue; if (grid[time % 2][next_r][next_c] == '.') { // visited continue; } if (grid[time % 2][next_r][next_c] == '1' || grid[time % 2][next_r][next_c] == '2') { // cheese edge grid[time % 2][next_r][next_c]++; if (grid[time % 2][next_r][next_c] == '3') { grid[1 - time % 2][next_r][next_c] = '0'; cheese_num--; } continue; } DFS(time, next_r, next_c); } } void printGrid(int time) { for (int r = 0; r < N; r++) { for (int c = 0; c < M; c++) { putchar(grid[time % 2][r][c]); putchar(' '); } putchar('\n'); } putchar('\n'); } int main(void) { getInput(); int time = 0; while (cheese_num) { memcpy(grid[1 - time % 2], grid[time % 2], 100 * 100); DFS(time, 0, 0); //printGrid(time); time++; } printf("%d", time + 1); return 0; }

제출 #126296

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: