[C] 백준 - 7576번: 토마토

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

7576번: 토마토

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

 

최초 생각 정리

- 이전에 풀이했던 "2178번: 미로 탐색" 문제의 풀이와 기본적으로 비슷한 풀이를 예상

- 특히 bfs 방식으로 풀이를 진행하며

- 입력은  M, N과 토마토들의 상태를 입력받고,

- 중간에서 bfs 함수안에서는 배열을 활용한 q를 이용해서 갱신해주고

- 출력은 토마토가 모두 익지 못하는 경우에만 -1을 출력 / 나머지 경우에는 0부터 누적합을 해준 값을 출력

[C] 백준 - 2178번: 미로 탐색

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

 

문제점

	int days = 0;
	int count = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (days < visited[i][j])
			{
				days = visited[i][j];
			}
			if (box[i][j] == 0)
			{
				count = 1;
			}
		}
	}

	if (count == 1)
	{
		printf("-1");
	}
	else
	{
		printf("%d", days);
	}

1. 최종 출력 부분에서 토마토가 모두 익을 최소날짜 혹은 모두 익지 못하는 경우 -1의 출력이 헷갈림

-> 풀이참조

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

 

풀이

(풀이참조 -> https://hading.tistory.com/174 )

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int M, N;

int box[1001][1001];
int visited[1001][1001];

int q[1000001][2];
int front = 0;
int rear = 0;

int move_of_x[4] = { -1, 1, 0, 0 };
int move_of_y[4] = { 0, 0, -1, 1 };

void bfs(void)
{
	while (front < rear)
	{
		int x = q[front][0];
		int y = q[front][1];
		front++;

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

			if (next_x >= 1 && next_y >= 1 && next_x <= N && next_y <= M && box[next_x][next_y] == 0)
			{
				box[next_x][next_y] = 1;
				visited[next_x][next_y] = visited[x][y] + 1;
				q[rear][0] = next_x;
				q[rear][1] = next_y;
				rear++;
			}
		}
	}
}

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			box[i][j] = -1;
			visited[i][j] = 0;
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			scanf("%d", &box[i][j]);

			if (box[i][j] == 1)
			{
				q[rear][0] = i;
				q[rear][1] = j;
				rear++;
			}
		}
	}

	bfs();

	int days = 0;
	int count = 0;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			if (days < visited[i][j])
			{
				days = visited[i][j];
			}
			if (box[i][j] == 0)
			{
				count = 1;
			}
		}
	}

	if (count == 1)
	{
		printf("-1");
	}
	else
	{
		printf("%d", days);
	}

	return 0;
}

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