Search
Duplicate

토마토

주차
0주차
문제번호
7576
언어
티어
실버
유형
그래프
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties
접근 방법
가로, 세로의 크기가 각각 1000 이므로 익은 토마토 주위로 토마토를 익힌 다음에 모든 격자의 토마토를 계산하기에는 시간이 너무 많이 소요됩니다. 따라서 이미 익은 토마토들의 좌표의 정보를 큐에 저장해 놓고 BFS를 통해 익힌 다음에 (현재 일 + 1) 만큼을 익혀진 토마토들의 좌표에 저장해 놓음으로써 최소 일수를 구할 수 있다고 생각했습니다.
#include <iostream> #include <vector> #include <queue> int N, M, exception_value1, exception_value2, num_tomato; std::vector<std::vector<int> >tomato; std::queue<std::pair<int, int> >q; std::vector<std::vector<int> >visited; std::vector<std::pair<int, int> > dir; void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> M >> N; tomato.resize(N, std::vector<int>(M, 0)); exception_value1 = 0; num_tomato = 0; visited.resize(N, std::vector<int>(M, 0)); dir = {{0, 1} , {1, 0}, {-1, 0}, {0, -1}}; for (size_t i = 0 ; i < N ; i++) for (size_t j = 0 ; j < M ; j++) { std::cin >> tomato[i][j]; if (tomato[i][j] == 1) { q.push({i, j}); exception_value1 ++; } if (tomato[i][j] != -1) num_tomato++; } } int exception_check() { if (exception_value1 == num_tomato) return (-1); return (0); } void print_val(int n) { if (n == -1) std::cout << 0; else if (n == -2) std::cout << -1; else std::cout << n; } void solve() { int retrn_val; int date = 0; int x, y; int q_x, q_y; int max_date = -1; std::pair<int, int> a; if ((retrn_val = exception_check())) { print_val(retrn_val); return; } while (!q.empty()) { a = q.front(); q.pop(); y = a.first; x = a.second; date = visited[y][x]; for (size_t i = 0 ; i < 4 ; i++) { q_y = y + dir[i].first; q_x = x + dir[i].second; if (q_x < 0 || q_x >= M || q_y < 0 || q_y >= N || visited[q_y][q_x] || tomato[q_y][q_x] != 0) continue; visited[q_y][q_x] = date + 1; if (max_date < visited[q_y][q_x]) max_date = visited[q_y][q_x]; tomato[q_y][q_x] = 1; q.push({q_y , q_x}); } } exception_value2 = 0; for (size_t i = 0; i < N ; i++) { for (size_t j = 0 ; j < M ; j++) { if (tomato[i][j] == 1) exception_value2++; } } if (exception_value2 != num_tomato) max_date = -2; print_val(max_date); } int main() { input(); solve(); return (0); }
C++
복사