[알고리즘] 백준 7576번: 토마토 (C++), 간만에 느낀 성취감 있는 풀이

이번 문제 풀이는 못 풀어서 다른 사람의 답을 참고했음에도 성취감을 느낄 수 있었다.

 

주석처리가 이번 문제의 성취감 포인트였던 거 같다.

 

기존의 문제 풀이 방식

for문을 사용하여 1일 때, BFS를 사용하면 한 번에 모든 0인 노드를 다 순회하기 때문에 다른 접근법이 필요했다.

떠올랐던 방법이 for문을 사용하여 1일 때, BFS를 사용하지 않고, 큐에다가 그 노드를 push 한다.

 

그리고 난 뒤에 BFS를 실행시키면 답에 접근할 수 있었다.

하지만, 또 다른 문제가 발생한다. 

 

현재까지의 접근법으로 작성한 코드는 이렇다.

// 궁금증 1: 굳이 이번 문제에 visited가 필요했을까
// 궁금증 2: bfs의 if 조건문에서 map이 1인 경우는 따져도 되지 않을까

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, m;
int map[1001][1001] = { 0, };
bool visited[1001][1001] = { 0, };
int cnt = 0;
// queue의 push 방식이 이번 문제의 포인트이지 않을까
queue<pair<int, int>> q;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1,0},{1, 0}, {0, -1}, {0, 1} };

void bfs() {
	if (q.empty()) {// 박스 안에 익어있는 토마토가 하나도 없는 경우
		return;
	}

	// cnt를 무작정 하나씩 증가시키는 것이 이상하다고 생각이 들었다.
	// 네 방향을 검토했을 때 익힐 것이 없다면 cnt를 시키지 말아야 한다.
	// 그래서 하나라도 익힐 것이 있었을 때를 판단하기 위해 flag 변수를 선언했다.
	bool flag = 0;

	while (!q.empty()) {
		flag = 0;

		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (!visited[dy][dx] && map[dy][dx] == 0) {
					visited[dy][dx] = 1;
					map[dy][dx] = 1;
					q.push(make_pair(dy, dx));
					cout << dy << ' ' << dx << '\n';
					flag = 1;
				}
			}
		}
		cout << '\n';
		// 이 곳에 cnt를 쓴 이유는 네 방향을 모두 고려한 뒤 익힐 것이 있으면
		// 모두 익히는 것에 하루를 지났기 때문에 cnt++을 해주었다.
		if(flag == 1){
			cnt++;
		}
	}
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}

	// bfs인데 한 번에 모든 데이터를 처리하지 않는 (모든 데이터를 순회하지 않는)
	// 조건이 필요하다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j] && map[i][j] == 1) {
				visited[i][j] = 1;
				q.push(make_pair(i, j));
				// q에 들어간 것이 없다면? bfs는?
			}
		}
	}

	bfs();
	// 0이 있는지 탐색 >> -1 출력

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) {
				cout << -1;
				return 0;
			}
		}
	}

	cout << cnt;
	return 0;
}

---

주석 처리 & 애매한 부분 출력(디버깅)

이번 문제에서 틀렸음에도 불구하고, 성취감을 느낄 수 있었던 게 주석 처리였다고 했다.

평소 같았으면 '왜 안 될까?'가 떠오르는 문제였지만 '이 부분에서 무엇이 문제일까?'라는 논리적인 접근이 가능해진다.

 

발생했던 또 다른 문제는 다음 사진을 가지고서 설명한다.

내가 짠 논리대로 라면 '3 5'와 '4 4' 사이에 줄 넘김이 없어야 한다. 즉, 저 주황색 네모 박스가 하나로 처리되어야 답에 도달할 수 있었다.

 

주석 처리와 애매한 부분 출력(디버깅)으로 기존 코드의 문제가 무엇인지 빠르게 파악할 수 있었다. 

기존에 내가 바랬던 BFS처리를 그림으로 나타내면 이렇다.

빨간색 = 1번째

보라색 = 2번째

파란색 = 3번째

 

하지만 내 코드가 처리하고 있던 일은 이렇다.

빨간색 = 1번째

보라색 = 2번째

파란색 = 3번째

주황색 = 4번째

 

그래서 '이걸 어떻게 처리해야 하나' 하면서 처리할 수 있게 변수들을 여러 가지 추가하는데 코드가 더욱 복잡해지고, 스스로 해석이 힘들 정도로 변수를 많이 추가했었다.

 

너무 복잡한 풀이를 요구하지는 않는 거 같아서 다른 사람의 풀이를 참고했다.

https://jdselectron.tistory.com/55

[백준 7576, c++] 토마토(bfs)

 

평소보다 더 논리 정연하게 접근해서 그런지 더 빠르게 문제점이 무엇인지 이에 대한 솔루션은 어떤 게 있는지 파악할 수 있었다.

 

내 풀이 방식이 4가지 방향을 고려하고 나서 cnt++를 하는 방식이었다면 

참고한 풀이는

'map[dy][dx] = map[y][x] + 1'의 방식으로 map이란 배열 자체에 시작이 1이라면 얼마나 떨어져 있는지 나타낼 수 있는 방법이었다.

(이와 비슷한 방법을 다른 문제에서 사용한 거 같아 찾아보았다.)

https://www.acmicpc.net/problem/1697

1697번: 숨바꼭질

---

이번 문제의 포인트

1. BFS를 돌리는 시점과 큐에 push 하는 방식 >> 확실히 BFS가 어떻게 돌아가는지 알고 있어야 한다.

2. map[dy][dx] = map[y][x] + 1

 

---

소스 코드

// 궁금증 1: 굳이 이번 문제에 visited가 필요했을까
// 궁금증 2: bfs의 if 조건문에서 map이 1인 경우는 따져도 되지 않을까

#include <iostream>
#include <vector>
#include <queue>
#include <utility>
using namespace std;

int n, m;
int map[1001][1001] = { 0, };
bool visited[1001][1001] = { 0, };
// queue의 push 방식이 이번 문제의 포인트이지 않을까
queue<pair<int, int>> q;

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1,0},{1, 0}, {0, -1}, {0, 1} };

void bfs() {
	if (q.empty()) {// 박스 안에 익어있는 토마토가 하나도 없는 경우
		return;
	}

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (!visited[dy][dx] && map[dy][dx] == 0) {
					visited[dy][dx] = 1;
					map[dy][dx] = map[y][x] + 1;
					q.push(make_pair(dy, dx));
					//cout << dy << ' ' << dx << '\n';
				}
			}
		}
		//cout << '\n';
	}
}

int main() {
	cin >> m >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int idx;
			cin >> idx;
			map[i][j] = idx;
		}
	}

	// bfs인데 한 번에 모든 데이터를 처리하지 않는 (모든 데이터를 순회하지 않는)
	// 조건이 필요하다.
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (!visited[i][j] && map[i][j] == 1) {
				visited[i][j] = 1;
				q.push(make_pair(i, j));
				// q에 들어간 것이 없다면? bfs는?
			}
		}
	}

	bfs();
	// 0이 있는지 탐색 >> -1 출력

	bool flag = 0;
	int max = 0;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (map[i][j] == 0) {
				flag = 1;
			}
			else {
				if (map[i][j] > max) {
					max = map[i][j];
				}
			}
		}
	}

	if (flag == 1) {
		cout << -1;
	}
	else {
		cout << max - 1; // 기존에 있던 익은 토마토의 값이 1이라서 1을 빼준 값으로 출력
	}

	return 0;
}

---

느낀 점

스스로도 주석 정리와 애매한 부분 출력(디버깅)을 통해 문제를 풀어야 하는 것이 중요함을 알고 있었다.

재차 느낄 수 있었던 건 확실히 알고 있다 하더라도 주석으로 처리시켜 두는 것이 문제를 풀 때 더 편하구나를 느낄 수 있었다.

(그래도 아직 DP는 어렵다😅)