일단 이 문제를 처음 풀었던 때의 코드를 첨부함…
//아기 상어 - 골드 3
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
//상, 좌, 하, 우
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
vector<vector<int>> board;
int n, fish_cnt = 0, shark_size = 2, eat_cnt = 0;
pi shark_cur;
bool comp(pi a, pi b) {
if (a.first == b.first) return a.second < b.second;
return a.second < b.second;
}
int solve() {
int ans = 0;
while (fish_cnt) {
queue<pi> q;
vector<vector<bool>> visited(n, vector<bool> (n, false));
bool found = false;
q.push(shark_cur);
int time = 0;
visited[shark_cur.first][shark_cur.second] = true;
while (!q.empty()) {
vector<pi> possible;
int len = q.size();
time++;
for (int j = 0; j < len; j++) {
int x = q.front().first, y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
if (board[nx][ny]) {
//나보다 큰 물고기 -> 못 지나감
if (board[nx][ny] > shark_size) continue;
if (board[nx][ny] < shark_size) {
possible.push_back({nx, ny});
}
}
visited[nx][ny] = true;
q.push({nx, ny});
//나보다 작은 물고기 -> 먹고 그 쪽으로 이동, 만약 먹은 개수 차면 크기 키워주기
if (!possible.empty()) {
sort(possible.begin(), possible.end(), comp);
pi next = possible[0];
ans += time;
shark_cur = next;
board[next.first][next.second] = 0;
eat_cnt++;
if (eat_cnt == shark_size) {
eat_cnt = 0;
shark_size++;
}
fish_cnt--;
found = true;
}
}
if (found) break;
}
if (found) break;
}
if (!found) return ans;
}
return ans;
}
int main() {
cin >> n;
board.assign(n, vector<int> (n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
if (board[i][j] == 9) {
shark_cur = {i, j};
board[i][j] = 0;
}
else if (board[i][j]) fish_cnt++;
}
}
cout << solve();
}
자… 지금부터 제가 왜 틀렸는지 설명하겠습니다
먼저 정답코드부터
//아기 상어 - 골드 3
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
//상, 좌, 하, 우
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};
vector<vector<int>> board;
int n, fish_cnt = 0, shark_size = 2, eat_cnt = 0;
pi shark_cur;
bool comp(pi a, pi b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
}
int solve() {
int ans = 0;
while (fish_cnt) {
queue<pi> q;
bool found = false;
q.push(shark_cur);
int time = 0;
vector<vector<bool>> visited (n, vector<bool> (n, false));
while (!q.empty()) {
vector<pi> possible;
int len = q.size();
time++;
for (int j = 0; j < len; j++) {
int x = q.front().first, y = q.front().second;
q.pop();
visited[x][y] = true;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= n || visited[nx][ny]) continue;
if (board[nx][ny]) {
//나보다 큰 물고기 -> 못 지나감
if (board[nx][ny] > shark_size) continue;
if (board[nx][ny] < shark_size) {
possible.push_back({nx, ny});
}
}
visited[nx][ny] = true;
q.push({nx, ny});
}
}
//나보다 작은 물고기 -> 먹고 그 쪽으로 이동, 만약 먹은 개수 차면 크기 키워주기
if (!possible.empty()) {
sort(possible.begin(), possible.end(), comp);
pi next = possible[0];
ans += time;
shark_cur = next;
board[next.first][next.second] = 0;
eat_cnt++;
if (eat_cnt == shark_size) {
eat_cnt = 0;
shark_size++;
}
fish_cnt--;
found = true;
}
if (found) break;
}
if (!found && fish_cnt) return ans;
}
return ans;
}
int main() {
cin >> n;
board.assign(n, vector<int> (n, 0));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> board[i][j];
if (board[i][j] == 9) {
shark_cur = {i, j};
board[i][j] = 0;
}
else if (board[i][j]) fish_cnt++;
}
}
cout << solve();
}
일단 진짜 맨 처음에는 그냥 순서를 상 좌 우 하 로 설정하면 별도의 정렬 없이 맞는 거 아닐까연^^ 했는데 아니라서 그거 수정했고
- comp 함수에서 return a.first < b.first로 해줘야 함 당연함,,,
- possible 배열 empty 아닐 때 탐색하는 거 아예 한 타임이 끝나고 수행해야 함. 왜냐하면 한 타임에서 가능한 좌표가 여러 개 나올 수 있기 때문. 틀린 코드는 한 좌표에서 위! 하고 possible 있으면 이동 아래! 하고 possible 있으면 이동 이런 식으로 완전히 순서가 잘못됨
근데 의외로 틀린 이유는 이게 끝임. ㅋㅋㅋㅋㅋㅋ 그래서 좀 허무함 하…
대신 뭐랄까… 이런 복잡한 구현 할 때에는 수도코드로 먼저 어떻게 구현할지 정리 한 다음에 들어가는 게 좋다는 생각이 들었음.
이 문제 다시 풀면서 그렇게 풀어서 도움 받기도 했고, 또 특히 이 문제는 괄호 안에 괄호 이래서 부분부분을 정리해두지 않으면 뭐가 뭔지 잘 알기 힘들기 때문에…
내가 쓴 수도코드를 여기 적어둠.
물고기 있는 동안 :
visited 선언
!q.empty() :
움직이기 : visited skip
가능한 애들 따로 분류
계속 하다가 가능한 애들 생기면 :
순위 매겨서 맨 위에 애 선택, 위치 이동.
이동하면 break.
q 비었는데도 이동 안했으면 더 이상 물고기가 없는 거
-> return.
아무쪼록 구현 연습에 좋은 문제였다고 생각하고… 저 스스로에게는 테케 넣고 일일히 노가다 뛰면서 디버깅하기 힘든 문제를 마주쳤을 때 근본적인 로직을 다시 살펴보면서 틀린 점을 찾아내는 방법을 연습할 수 있는 기회였습니다… 그리고 그 방법은 앞서 말했듯이 수도코드 정리해서 한 번 써보기