인프런 커뮤니티 질문&답변

안녕하세요. 선생님! 명절 연휴 잘 보내셨나요?

다름이 아니라.. 제가 작성한 코드가 -1이 발생하는 경우에 time_limit이 발생하는데.. 원인을 못 찾겠어서 이렇게 찾아왔습니다..ㅎㅎ

알고리즘 상 선생님과 다른 부분은 거의 없습니다.

dis배열에 거리를 판단하는게 아니라 그냥 map 배열에 거리를 늘려가면서 거리자체가 체크역할도 하는 것입니다. map에 덧씌워서 하기 때문에 초기거리값은 1부터 시작해야 했고 마지막 거리를 출력할 땐 -1을 해서 출력하도록 하였습니다.

그리고 -1을 출력하는 경우는 모두 다 훑어서 0이 나오면 -1을 출력하는 방식이 아니라 처음 map배열을 입력받을 때, 0의 개수를 파악해놓은 다음 0을 처리할때마다 감소시켜서 이값이 하나라도 남아있으면 0보다 크므로 0이 아닐때 -1을 출력하도록 하였습니다..

이렇게 그냥 부수적인 처리방식만 다를뿐.. 어디서 dfs를 타임리밋 뜨게 하는지 도통 모르겠습니다.. ㅠ 

//[쟁점] 매 토마토마다 새로운 배열로 초기화해야 하나? 주객전도x
//BFS에서 time_limit이 발생하는 이유는 ?

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>
using namespace std;
int map[1005][1005];	//거리를 한꺼번에 표시. 0은 익지 않은 토마토인 동시에 방문하지 않은 토마토
queue<pair<int, int > > q;
int maxval = -2147000000;
int dis;
int dr[4] = { 1, 0, -1, 0 };
int dc[4] = { 0, 1, 0, -1 };
int untom;
int main() {
	freopen("data.txt", "rt", stdin);
	int n, m;
	cin >> m >> n;
	for (int i = 0; i < n; i++) {	//map 입력 및 토마토 위치 파악
		for (int j = 0; j < m; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1)
				q.push(make_pair(i, j));
			else if (map[i][j] == 0)
				untom++;
		}
	}
	pair<int, int> fr;
	while (!q.empty()) {
		fr = q.front();
		q.pop();
		dis = map[fr.first][fr.second];
		if (maxval < dis)
			maxval = dis;
		for (int i = 0; i < 4; i++) {
			int rr = fr.first + dr[i];
			int cc = fr.second + dc[i];
			if (rr < 0 || rr >= n || cc < 0 || cc >= m)
				continue;
			if (map[rr][cc] == 0) {
				untom--;
				map[rr][cc] = map[fr.first][fr.second] + 1;
				q.push(make_pair(rr, cc));
			}
		}
	}
	if (untom == 0)
		cout << maxval - 1 << endl;
	else
		cout << -1 << endl;
}