7576 토마토 - 방법1

 

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

7576번: 토마토

BFS 개념 공부 후 처음 풀어본 BFS 문제이다.

며칠 동안 하루 1시간 정도씩 해봤던 것 같다. (좀 진득하게 봤었어야 했는데 시간이 길게 안 났음,,)

하다 하다가 뭔가 이상해서....?

그냥 멘토님 소스 참고했다. 그래도 며칠 고민했으니깧ㅎ

아직 익숙하지가 않아서 남 소스 분석하는 것만으로도 머리가 좀 아팠당...

---

내 생각 흐름

문제 읽으면서 내 생각을 바로바로 정리한 메모장이다.

브레인스토밍 식으로 생각나는 거 바로바로 적었는데, 적다 보면 생각이 좀 더 구체화되고 하나하나가 단서로 작용할까 싶어서 적어뒀었다.

 

*고민사항

큐를 어떻게 사용해야 하는가로 엄청난 고민을 했다... bfs니까 큐를 써야겠는뎈ㅋㅋ어디다 뭘 어떻게 적용하지??로 고민을 좀 했었다.

데이터를 입력받은 배열 arr의 데이터를 조작해야 하지 않을까? 생각했다.

그리고 날짜를 어떻게 세어줘야 하지?? 도 생각 오래 함..

방문처리를 굳이 왜 해줘야 하지 싶었다. (난 애초에 arr을 조작하려고 했어서)

-> 지금 생각해보니까 arr을 조작하려면 조건이 더 필요하거나 이후 확인에서 좀 조심해야 할 것 같다. 안되면 말고

 

*시도

-main

arr에 데이터를 입력받는다.

arr에 1이 입력되면 함수 bfs를 호출해 인덱스 값을 넘긴다.

-bfs

일단 큐 생성- 얠 어떻게 써야 하는 거지..?

전역 변수 int cnt = 0; - bfs가 호출될 때마다 ++해볼까 생각함

->이렇게 하면 날짜를 세는 게 아니라 bfs 호출 횟수를 세는 격.

이런 식으로 계속 날짜 갖고 고민하다가 일단 날짜 생각 안 하고 품

이후 동서남북의 위치가 정해진 범위를 넘기는지 확인하고,

0인 경우 1로 값을 바꿔주려 함  -일종의 방문처리를 노림

if (row < N) {
		if (arr[row + 1][col] == 0) { //동
			arr[row + 1][col] = 1;

		}
	}
	if (col < M) {
		if (arr[row][col + 1] == 0) { //남
			arr[row][col+1] = 1;

		}
	}
	if (row != 0) {
		if (arr[row - 1][col] == 0) { //서
			arr[row - 1][col] = 1;

		}
	}
	if (col != 0) {
		if (arr[row][col - 1] == 0) { //북
			arr[row][col - 1] = 1;

		}
	}

 

이런 식으로 쭉쭉하다가 될 거 같으면서도 안될 거 같고 그놈의 날짜를 어떻게 해야 될까 싶어서

그냥 답을 봤다.

 

분석 및 고치기

답 소스 보고 분석하고 분석 사항을 정리한 뒤 내 소스를 분석하면서 다시 짠 소스다.

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

struct loc {
	int x, y;
};

int visited[1000][1000];
vector<int> arr[1000];
queue<loc> q;
//int cnt = 0;
int M, N;
//동, 서, 남, 북
int dn[4] = { 1,-1,0,0 };
int dm[4] = { 0,0,1,-1 };

void bfs();

int main() {
	int cnt = 0; //처음부터 다 익어있었는지 확인해줌
	cin >> M >> N;
	
	//데이터 입력받음
	int temp;
	for (int i = 0; i < N; i++) { //row
		for (int j = 0; j < M; j++) { //col
			cin >> temp;
			arr[i].push_back(temp);	//arr은 순전히 정보 제공, 중간에 데이터가 변경되지 않는다 ->visited가 변경
			if (temp == 1) {
				q.push({ i,j });	//익은 토마토의 좌표를 입력한다
				visited[i][j] = 1;
			}
			cnt++; //입력되는 토마토의 수
		}
	}

	//처음부터 익어있었는지 확인
	int chk = 0;
	for (int i = 0; i < N; i++) { //row
		for (int j = 0; j < M; j++) { //col
			if (arr[i][j] == 1) {
				chk++;
			}
		}
	}		
	if (cnt == chk) {
		cout << 0;
	}

	//토마토 익히기 시작
	//1이 나올때마다 bfs로 할 필요 없이 큐에 넣은 후 bfs에서 처리하면 돼
	bfs();

	//익었는지 검사한다
	int ripe = -1;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (arr[i][j] == 0 && visited[i][j] == 0) {	//토마토가 있는데 방문하지 못한 상황 ex. 주위에 갇힘
				cout << -1;
				return 0;
			}
			ripe = ripe < visited[i][j] ? visited[i][j] : ripe;
		}
	}
	cout << ripe - 1; //처음 1을 뺀다

	return 0;
}
//circles- 노래 좋음
void bfs() {
	//queue<int> q;
	//cnt++; //호출이 됨 - 날짜를 세야하니까// 일단 이렇게 하면 안됨
	//원래 하려던대로 1이 나올때마다 부르기 + 이렇게 cnt세면 1이 나온 수를 세는 격임

	//동서남북 
	while (!q.empty()) {
		loc front = q.front();
		q.pop();

		//if (arr[front.x][front.y] == 1) {	} //어차피 이거 1인거만 들어있어서 필요없
		for (int a = 0; a < 4; a++) {
			int nextn = front.x + dn[a];
			int nextm = front.y + dm[a];
			//범위 확인
			if (nextn < 0 || nextn >= N || nextm < 0 || nextm >= M) {
				//c++언어의 특성을 고려하면 안될때를 걸르는게 나음. 되는거 하다가 앞 조건이 안되면 뒤도 안됨 feat프언
				continue;
			}

			//방문 확인 && 토마토 있는지 확인
			if (visited[nextn][nextm] == 0 && arr[nextn][nextm] == 0) { //방문안했고 토마토도 있을 경우
				visited[nextn][nextm] = visited[front.x][front.y] + 1;
				q.push({ nextn, nextm });
			}
		}
	}

	/*나는 되는 조건 하에 토마토가 있는지 확인한후 해당 위치를 1로 변경시키고, 날짜 세는 애를 또 따로 만들어주려함\
	이렇게 생각하면 visited 배열이 있는게 낫겠다.\
	또한 visited는 데이터가 직접적으로 변동되는 애임*/
 }

(흠.. 큐를 쓰지 않고 bfs에 인덱스 값을 직접적으로 넘겨줬다면 그거대로 할 수 있긴 있었을 것 같다...)

 

결론

BFS의 핵심 요소는 연결된 값, 큐 사용처, 방문처리인 것 같다.

아직 큐를 어디에 써야 하는지 감이 안 오고, 방문처리를 어떻게 해야 효율적으로 잘하는 건지 잘 모르겠다.

처음 풀어본 거니까 그럴 수 있지!!

피드백 : 큐는 다음 날짜에 방문할 토마토 후보를 넣고 있다.