[C] 백준 - 2468번: 안전 영역

7월 28일(금) - 그래프와 순회 (2468번)

2468번: 안전 영역

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 이전에 풀이했던 "1012번: 유기농 배추" 혹은 "2667번: 단지번호붙이기"문제와 유사한 풀이를 예상

- dfs 방식으로 풀이를 진행하며

 

- 입력은 N과 N x N개의 2차원 배열을 area[ ][ ]에 받는다

   하지만 내릴 수 있는 비의 양 = 즉 depth 를 0부터 100까지 모두 돌리는 것은 비효율적일 것 이므로

   2차원 배열을 입력받으면서 각각의 영역의 높이 중 최댓값인 max_depth값도 찾아놓는다

- for문을 0부터 max_depth까지 돌리면서

   flood_judge라는 함수를 돌려서, depth에 따라서 침수되지 않은 영역만 safe_area[ ][ ]에 기존 높이를 복사하고

   침수되는 영역은 safe_area[ ][ ]에서 0으로 설정해준다

- depth에 해댱하는 safe_area를 만들어놓았다면, 이중 for문을 돌리면서 dfs 호출

   +안전 영역은 변수 safe_count에다가 카운팅한다

- 출력은 depth마다 safe_count의 값들 중에서 최댓값을 저장해놓은 변수 result를 출력

[C] 백준 - 1012번: 유기농 배추

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

for (int depth = 0; depth <= max_depth; depth++)
	{
    		// depth마다 초기화해주는 코드 start
		int safe_count = 0;
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				safe_area[i][j] = 0;
				visited[i][j] = 0;
			}
		}
        	// 초기화 코드 end

		flood_judge(depth);
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				...
			}
		}

		result = (safe_count > result) ? safe_count : result;
	}

1. safe_area[ ][ ]와 visited[ ][ ] 그리고 변수 safe_count를 depth마다 초기화해주는 부분 없이 처음에 코드 작성

-> 예제1은 5x5사이즈 그래도인 25가, 예제2에서는 왜인지 모르겠지만 41이 잘못 출력되는 문제가 발생

-> depth마다 초기화해주는 부분의 코드를 추가하며 해결

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#define MAX(x, y) (((x) > (y)) ? (x) : (y))

#include <stdio.h>

int N;
int total_area[101][101];
int safe_area[101][101];
int visited[101][101];

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


void flood_judge(int depth)
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (total_area[i][j] > depth)
			{
				safe_area[i][j] = total_area[i][j];
			}
			else // total_area[i][j] <= depth 인 상황 , 즉 침수되는 상황
			{
				safe_area[i][j] = 0;
			}
		}
	}
}

void dfs(int y, int x)
{
	visited[y][x] = 1;

	for (int i = 0; i < 4; i++)
	{
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_y < 0 || next_x >= N || next_y >= N)
		{
			continue;
		}
		if (safe_area[next_y][next_x] != 0 && visited[next_y][next_x] == 0)
		{
			dfs(next_y, next_x);
		}
	}
}

int main(void)
{
	scanf("%d", &N);

	int max_depth = -1;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &total_area[i][j]);
			
			if (max_depth < total_area[i][j])
			{
				max_depth = total_area[i][j];
			}
		}
	}

	int result = 0;
	for (int depth = 0; depth <= max_depth; depth++)
	{
		int safe_count = 0; // depth가 늘어날때마다, safe_area[][]와 visited[][], 변수 safe_count를 초기화해주어야한다
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				safe_area[i][j] = 0;
				visited[i][j] = 0;
			}
		}

		flood_judge(depth); // depth마다 새로운 safe_area[][]를 만들어주며,
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < N; j++)
			{
				if (safe_area[i][j] != 0 && visited[i][j] == 0)
				{
					dfs(i, j); // dfs를 돌리며 새로운 visited[][]를 만들고,
					safe_count++; // 새로운 safe_count를 카운팅해주어야한다
				}
			}
		}

		result = (safe_count > result) ? safe_count : result;
        	// depth마다 카운팅한 safe_count는, 직전 depth까지의 최댓값인 result와 대소비교하여 갱신한다
	}

	printf("%d", result);
	return 0;
}

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ