백준 7576. 토마토[실패]

1.실패 원인

bfs 구성이나 좌표 설정, 연결 요소 같은 부분은 계속 해왔으니까 제대로 작성을 했지만..

몇가지 조건이 더 추가됐더니 제대로 된 답을 도출해내지 못했다. 깊게 생각을 못한것같다.

이번 문제는 조건과 접근 방법은 모두 제대로 생각해냈는데 구현능력이 떨어져서 실패했다.

이건 그래프 단원의 문제라서가 아니라 알고리즘 공부를 제대로 하지 않아서 실패한 것같다.

 

2.작성 코드

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

int M, N;
int arr[1001][1001];
int cpyarr[1001][1001];
bool bvisit[1001][1001] = { false, };

int DIRX[4] = { -1,0,1,0 };
int DIRY[4] = { 0,1,0,-1 };
int answer = 0;
int counted = 0;
struct Coord {
	int x;
	int y;
};
vector<Coord> vNext;

void bfs() {

	
	while (!vNext.empty()) {
		
		Coord c;
		c = vNext.back();
		vNext.pop_back();
		
			int strX = c.x;
			int strY = c.y;
			bvisit[strY][strX] = true;
			
			
			for (int i = 0; i < 4; i++) {

				int dirx = strX + DIRX[i];
				int diry = strY + DIRY[i];
				
				if (arr[diry][dirx] == 0 && dirx >= 0 && dirx < M && diry >= 0
					&& diry < N && !bvisit[diry][dirx]) {
					Coord nc = { dirx,diry };
					vNext.push_back(nc);
					bvisit[diry][dirx] = true;
					cpyarr[diry][dirx] = 1;
					answer++;
				}
			}
			
		
		
	}

}

int main() {
	
	cin >> M >> N;
	for (int j = 0; j < N; j++)
		for (int i = 0; i < M; i++)
			cin >> arr[j][i];

	memcpy(cpyarr, arr, sizeof(arr));
	int subcount = 0;
	int total = M * N;
	for(int j=0; j<N;j++)
		for (int i = 0; i < M; i++)
		{
			if (arr[j][i] == 1) {
				Coord coord = { i,j };
				vNext.push_back(coord);
				subcount++;
			}
			else if (arr[j][i] == -1) {
				total--;
			}
		}
	if (subcount == total) cout << 0 << endl;
	else {
		bfs();
		int anscount = 0;
		for(int j=0; j<N;j++)
			for (int i = 0; i < M; i++) {
				if (cpyarr[j][i] == 1) {
					anscount++;
				}
			}
		if (anscount != total) {
			cout << total << endl;
			cout << anscount << endl;
			cout << -1 << endl;
		}
		else {
			cout << answer << endl;
		}
	}


	return 0;
}

3.참고 코드

https://sihyungyou.github.io/baekjoon-7576/

백준 7576번 : 토마토

4. 해결 방안

꾸준히 푸는방법밖에 답이 없을듯하다.