-
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
안녕하세요. 선생님
20.01.27 21:56 작성 조회수 110
0
안녕하세요. 선생님! 명절 연휴 잘 보내셨나요?
다름이 아니라.. 제가 작성한 코드가 -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;
}
답변을 작성해보세요.
0
0
김태원
지식공유자2020.01.27
멋진 코드입니다. ^^
제 컴퓨터에서 채점해보니 백점이 나옵니다. 알고리즘 상으로 문제가 없는 코드입니다.
채점하는 컴퓨터의 성능에 따라 토마토 문제는 4, 5번 데이터가 시간초과 될 수 있습니다.
간혹 시간초과 난다는 질문을 하더라구요.
별도로 데이터를 복사 붙여넣고 4, 5번 직접실행해 보니 답도 정확하게 출력됩니다.
드린 폴더에서 in4.txt 내용을 복사해 data.txt에 붙여넣기 하고 실행해 보세요. 답은 제대로 나올겁니다.
답변 2