[boj][c++] 7576 토마토

7576 토마토

bfs 연습문제로 풀어본 문제
코드를 참고한 뒤에 '아, 나 이 문제를 접해본 적이 있구나.' 싶었어서 현타왔다. 알고리즘 스터디 하면서 나왔던 난이도 중상짜리 문제와 푸는 방식이 비슷했다. bfs/dfs의 코드 구현은 대부분 비슷하기 때문에 문제풀이를 위해서는 미묘한 포인트를 잡는 것이 중요한데 그걸 못한게 아쉽다.

• 입력받을 때 값이 1인 노드를 큐버퍼에 넣는다.
• bfs함수가 시작되면 바로 큐에서 pop한 뒤에 인접 노드를 확인한다.
• 인접 노드가 박스 범위 내이고 비었다면 pop한 노드 값 + 1을 저장한다.
• 큐 버퍼가 빌때까지 이 과정을 반복한다.

위의 그림은 각각의 예시에서 토마토가 며칠에 거쳐 익게 되는지 손으로 계산해본 표이다. 내가 설명한 로직대로 코드를 짜게 되면 저런 과정을 거쳐서 토마토가 익게 된다.

방문기록을 남기는걸 당연하게 생각했기 때문에 값을 더해준다는 생각을 못했다. 또한 토마토가 두개 이상일 때 어떻게 처리할지도 구상하지 못했는데 입력받을 때부터 버퍼에 값을 담아주면 동시에 여러 곳에서 시작할 수 있다는 아이디어를 얻어서 겨우 코드를 짤수있었다.

그렇게 짠 첫 코드는 완전히 틀렸다^^ 틀린 이유는 x좌표와 y좌표를 n과 m에 매칭해서 짜야 하는데 n과 m의 위치를 뒤바꿔서 작성했기 때문이었다. 좌표평면 + 2차원 배열에 대한 이해 부족으로 생긴 문제였다. 계속 고민하다가 깨닫고 수정했지만 참 간단한 부분에서 실수를 하게 돼서 부끄럽다.

#include	<iostream>
#include	<deque>
using namespace std;

int n, m;
int graph[1001][1001];
int xs[4] = { 0,0,1,-1 };
int ys[4] = { 1,-1,0,0 };
deque<pair<int, int>> q;

void bfs()
{
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop_front();
		for (int i = 0; i < 4; i++)
		{
			int nx = x + xs[i];
			int ny = y + ys[i];
			if (nx >= 1 && ny >= 1 && nx <= n && ny <= m)
			{
				if (graph[nx][ny] == 0)
				{
					graph[nx][ny] = graph[x][y] + 1;
					q.push_back({ nx,ny });
				}	
			}
		}
	}
}

int main()
{
	cin >> m >> n;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> graph[i][j];
			if (graph[i][j] == 1)
				q.push_back({ i,j });
		}
	}
	bfs();
	int max = 0;
	bool emp = false;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++) 
		{
			if (graph[i][j] == 0)
			{
				emp = true;
			}
			if (max < graph[i][j])
				max = graph[i][j];
		}
	}
	if (emp == false)
		cout << max - 1 << endl;
	else
		cout << "-1" << endl;
	return 0;
}

---

44444

이 문제 풀고 solved.ac 확인하다가 이런 기록을 발견했다. ㅋㅋ