Search
Duplicate

아기 상어

주차
0주차
문제번호
16236
언어
티어
골드
유형
구현
nj_Blog
nj_상태
이해도
풀이
사람
이해도 2
13 more properties

Memo

N의 크기가 작기 때문에, 배열 전체의 상태를 확인하는 데에 부담이 없었음.
어렵지 않은 BFS였지만, 사소한 실수로 시간이 많이 걸렸음.
상어가 먹을 수 있는 먹이는 존재하지만, 그 먹이들이 상어가 지나갈 수 없는 물고기들로 둘러쌓여 있는 경우에 대한 고려가 없었음. 예외는 항상 고려하기.

Code

제출 날짜

@3/12/2021

메모리

2024 KB

시간

0 ms
#include <iostream> #include <queue> #include <string.h> #include <tuple> int space[21][21]; int shark_i, shark_j, shark_size, shark_level; int N, ans; int g_dx[4] = {0, 1, 0, -1}; int g_dy[4] = {1, 0, -1, 0}; bool visited[21][21]; std::queue<std::tuple<int, int, int> >q; //shark i , shark j , time void input_faster() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); } void input() { input_faster(); std::cin >> N; for (int i = 1 ; i <= N ; i++) for (int j = 1 ; j <= N ; j++) { std::cin >> space[i][j]; if (space[i][j] == 9) { space[i][j] = 0; shark_i = i; shark_j = j; } } ans = 0; shark_size = 2; } int count_fishes() { int cnt = 0; for (int i = 1 ; i <= N ; i++) for (int j = 1 ; j <= N ; j++) if (space[i][j] && space[i][j] < shark_size) cnt++; return (cnt); } bool state_update(int f_t, int f_i, int f_j) { if (f_t != 10000) { shark_i = f_i; shark_j = f_j; space[shark_i][shark_j] = 0; shark_level++; if (shark_level == shark_size) { shark_size++; shark_level = 0; } ans+=f_t; return (1); } else return (0); } int bfs() { int q_i, q_j, q_t, f_i, f_j, f_t, dx, dy; f_i = 0; f_j = 0; f_t = 10000; q.push({shark_i, shark_j, 0}); visited[shark_i][shark_j] = 1; while(!q.empty()) { std::tuple<int, int, int> tmp = q.front(); q.pop(); q_i = std::get<0>(tmp); q_j = std::get<1>(tmp); q_t = std::get<2>(tmp); if (space[q_i][q_j] && space[q_i][q_j] < shark_size) { if (f_t > q_t) { f_t = q_t; f_i = q_i; f_j = q_j; } else if (f_t == q_t) { if (f_i > q_i) { f_i = q_i; f_j = q_j; } else if (f_i == q_i && f_j > q_j) f_j = q_j; } continue; } for (int x = 0 ; x < 4 ; x++) { dx = (q_i + g_dx[x]); dy = (q_j + g_dy[x]); if (visited[dx][dy] || dx <= 0 || dx > N || dy <= 0 || dy > N || space[dx][dy] > shark_size) continue; visited[dx][dy] = 1; q.push({dx, dy, q_t + 1}); } } return (state_update(f_t, f_i, f_j)); } void print_val() { std::cout << ans; } void solve() { while (count_fishes()) { memset(visited, 0, sizeof(visited)); q = std::queue<std::tuple<int, int, int> >(); if(!bfs()) break; } } int main() { input(); solve(); print_val(); return (0); }
C++
복사