[백준 16236번 C/C++] 아기 상어
[백준 16236번 C/C++] 아기 상어

https://www.acmicpc.net/problem/16236
해결전략
너비우선탐색 BFS
아기 상어가 물고기를 먹은 시점에 BFS를 다시 돌려야 한다.
처음 시도한 코드
#include <iostream> #include <vector> #include <queue> using namespace std; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int n; vector<vector<int>> v; int answer; bool success = false; struct Info{ int y, x, feed, sharkSize; }; void BFS(int startY, int startX, int feed, int size, int time) { int timeSpent = 0; queue<Info> Q; Q.push({ startY, startX, feed, size }); vector<vector<int>> duration(n, vector<int>(n, -1)); vector<vector<bool>> visited(n, vector<bool>(n, false)); duration[startY][startX] = 0; visited[startY][startX] = true; while (!Q.empty()) { int y = Q.front().y; int x = Q.front().x; int feed = Q.front().feed; int sharkSize = Q.front().sharkSize; Q.pop(); for (int i = 0; i < 4; i++) { int ny = y + dirY[i]; int nx = x + dirX[i]; if (ny < 0 || n <= ny || nx < 0 || n <= nx) continue; if (visited[ny][nx] == true) continue; if (sharkSize < v[ny][nx]) continue; if (sharkSize == v[ny][nx] || v[ny][nx] == 0) { Q.push({ ny, nx, feed, sharkSize }); // 이동만 함. duration[ny][nx] = duration[y][x] + 1; visited[ny][nx] = true; continue; } //cout << ny << ", " << nx << "\n"; // 물고기를 잡아먹는 경우 feed++; v[ny][nx] = 0; // 먹은 물고기 표시 duration[ny][nx] = duration[y][x] + 1; visited[ny][nx] = true; timeSpent = max(timeSpent, duration[ny][nx]); answer = max(answer, time + timeSpent); success = true; if (feed == sharkSize) { BFS(ny, nx, 0, sharkSize + 1, time + timeSpent); } else { BFS(ny, nx, feed, sharkSize, time + timeSpent); } } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; v.resize(n, vector<int>(n)); int startY, startX; for (int y = 0; y < n; y++){ for (int x = 0; x < n; x++) { cin >> v[y][x]; if (v[y][x] == 9){ startY = y; startX = x; v[y][x] = 0; // 상어가 처음 위치한 칸을 빈칸으로 설정 } } } BFS(startY, startX, 0, 2, 0); if (false == success){ cout << "0"; } else{ cout << answer << "\n"; } return 0; }
정답코드
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; struct Info { // 상어의 위치, 먹은 물고기 수, 상어의 크기, 경과 시간 int y, x, feed, sharkSize, time; }; int dirY[4] = { -1, 0, 1, 0 }; int dirX[4] = { 0, -1, 0, 1 }; int n; vector<vector<int>> v; // 공간의 상태를 나타내는 2차원 벡터 vector<vector<bool>> visited; // 방문 여부를 저장하는 2차원 벡터 int answer = 0; // 최종 결과(경과 시간)를 저장할 변수 void BFS(int startY, int startX) { queue<Info> Q; Q.push({ startY, startX, 0, 2, 0 }); // 초기 상어의 위치, 먹은 물고기 수, 크기, 시간을 큐에 삽입 visited[startY][startX] = true; // 시작 위치를 방문 처리 while (!Q.empty()) { int size = Q.size(); vector<Info> fish; // 먹을 수 있는 물고기를 저장할 벡터 for (int i = 0; i < size; ++i) { int y = Q.front().y; int x = Q.front().x; int feed = Q.front().feed; int sharkSize = Q.front().sharkSize; int time = Q.front().time; Q.pop(); // 먹을 수 있는 물고기를 발견한 경우 if (v[y][x] != 0 && v[y][x] < sharkSize) { fish.push_back({ y, x, feed, sharkSize, time }); continue; } for (int j = 0; j < 4; ++j) { // 상하좌우로 이동 int ny = y + dirY[j]; int nx = x + dirX[j]; if (ny < 0 || n <= ny || nx < 0 || n <= nx) continue; if (visited[ny][nx] || v[ny][nx] > sharkSize) continue; // 이동 불가능한 경우 visited[ny][nx] = true; // 방문 처리 Q.push({ ny, nx, feed, sharkSize, time + 1 }); // 큐에 삽입 } } // 먹을 수 있는 물고기가 있는 경우 if (!fish.empty()) { // 물고기를 시간, 행, 열 순으로 정렬 sort(fish.begin(), fish.end(), [](const Info& a, const Info& b) { if (a.time == b.time) { if (a.y == b.y) return a.x < b.x; return a.y < b.y; } return a.time < b.time; }); // 가장 우선순위가 높은 물고기를 먹음 int newY = fish[0].y; int newX = fish[0].x int newFeed = fish[0].feed + 1; int newSize = fish[0].sharkSize; int newTime = fish[0].time; if (newFeed == newSize) { newFeed = 0; newSize++; } v[newY][newX] = 0; // 먹은 물고기 제거 answer = newTime; // 시간 업데이트 visited.assign(n, vector<bool>(n, false)); // 방문 배열 초기화 Q = queue<Info>(); // 큐 초기화 Q.push({ newY, newX, newFeed, newSize, newTime }); visited[newY][newX] = true; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; v.resize(n, vector<int>(n)); visited.assign(n, vector<bool>(n, false)); int startY, startX; for (int y = 0; y < n; y++) { for (int x = 0; x < n; x++) { cin >> v[y][x]; if (v[y][x] == 9) { startY = y; startX = x; v[y][x] = 0; // 상어가 처음 위치한 칸을 빈칸으로 설정 } } } BFS(startY, startX); cout << answer << "\n"; return 0; }
'⭐ 코딩테스트 > 백준' 카테고리의 다른 글
[백준 2138번 C/C++] 전구와 스위치 (0) | 2024.05.20 |
---|---|
[백준 15685번 C/C++] 드래곤 커브 (0) | 2024.05.07 |
[백준 14499번 C/C++] 주사위 굴리기 (0) | 2024.05.04 |
[백준 1520번 C/C++] 내리막 길 (0) | 2024.04.23 |
[백준 7682번 C/C++] 틱택토 (1) | 2024.04.20 |
댓글
이 글 공유하기
다른 글
-
[백준 2138번 C/C++] 전구와 스위치
[백준 2138번 C/C++] 전구와 스위치
2024.05.20 -
[백준 15685번 C/C++] 드래곤 커브
[백준 15685번 C/C++] 드래곤 커브
2024.05.07 -
[백준 14499번 C/C++] 주사위 굴리기
[백준 14499번 C/C++] 주사위 굴리기
2024.05.04 -
[백준 1520번 C/C++] 내리막 길
[백준 1520번 C/C++] 내리막 길
2024.04.23
댓글을 사용할 수 없습니다.