[백준] 16236 아기 상어 C++
문제
코드
#include <iostream>
#include <queue>
using namespace std;
#define MAX 20
// 아기상어
// BFS: 모든 간선의 가중치가 1일 때 최단 경로 탐색
int N;
int shark_x, shark_y, eat_cnt, shark_size=2;
int min_dist, min_x, min_y, result;
int map[MAX][MAX], check[MAX][MAX];
// check 배열은 거리를 저장
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { -1, 1, 0, 0 };
// 물고기 좌표
struct info {
int x, y;
};
void bfs(int x, int y) {
queue<info> q;
// 지금 위치의 시간 = 0
check[x][y] = 0;
q.push({x, y});
while(!q.empty()) {
// 가장 앞에 있는 객체의 네 방향을 탐색
info cur = q.front();
q.pop();
int x = cur.x, y = cur.y;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위가 어긋난 경우 continue
if(nx<0 || nx>=N || ny<0 || ny>=N) { continue; }
// 이미 방문했거나 상어 크기보다 커도 continue
if(check[nx][ny]!=-1 || map[nx][ny]>shark_size) { continue; }
// (nx, ny)에 있는 물고기까지의 이동거리 갱신
check[nx][ny] = check[x][y] + 1;
// 먹을 수 있는 물고기라면
if(map[nx][ny]!=0 && map[nx][ny]<shark_size) {
// 이 과정은 맨 위, 맨 왼쪽 물고기부터 먹어야해서 검사하는 것
if(min_dist > check[nx][ny]) {
min_x = nx;
min_y = ny;
min_dist = check[nx][ny];
} else if(min_dist == check[nx][ny]) {
if(min_x == nx) {
if(min_y > ny) {
min_x = nx;
min_y = ny;
}
} else if(min_x > nx) {
min_x = nx;
min_y = ny;
}
}
}
// 다시 물고기 위치를 push
q.push({nx, ny});
}
}
}
int main() {
ios::sync_with_stdio(0);
int x, y;
cin >> N;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
cin >> map[i][j];
// 아기 상어의 위치를 알아내야 하기 때문
if(map[i][j] == 9) { shark_x=i; shark_y=j; map[i][j]=0; }
}
}
// 물고기 개수만큼 수행
while(1) {
min_dist = 400;
min_x = 20;
min_y = 20;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
check[i][j] = -1;
}
}
// 여기까지 BFS를 위한 정보 초기화 과정
// 처음엔 아기상어 자리를 인자로 bfs 호출
bfs(shark_x, shark_y);
// 먹을 수 있는 물고기라면
if(min_x != 20 && min_y != 20) {
// 이동시간을 result에 더해주고
result += check[min_x][min_y];
// 얼마나 먹었는지 증가시켜주고
eat_cnt++;
// 아기상어가 성장할 수 있는 경우인지 검사
if(eat_cnt == shark_size) {
shark_size++;
eat_cnt = 0;
}
// 물고기를 먹었으니까 0으로 초기화
map[min_x][min_y] = 0;
// 상어의 위치를 재조정
shark_x = min_x;
shark_y = min_y;
} else {
// 먹을 수 있는 물고기가 없는 경우라면 break
break;
}
}
cout << result << '\n';
return 0;
}
📢
#include <iostream>
#include <queue>
using namespace std;
#define MAX 20
// 아기상어
// BFS: 모든 간선의 가중치가 1일 때 최단 경로 탐색
int N;
int shark_x, shark_y, eat_cnt, shark_size=2;
int min_dist, min_x, min_y, result;
int map[MAX][MAX], check[MAX][MAX];
// check 배열은 거리를 저장
int dx[4] = { 0, 0, 1, -1 };
int dy[4] = { -1, 1, 0, 0 };
// 물고기 좌표
struct info {
int x, y;
};
void bfs(int x, int y) {
queue<info> q;
// 지금 위치의 시간 = 0
check[x][y] = 0;
q.push({x, y});
while(!q.empty()) {
// 가장 앞에 있는 객체의 네 방향을 탐색
info cur = q.front();
q.pop();
int x = cur.x, y = cur.y;
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
// 범위가 어긋난 경우 continue
if(nx<0 || nx>=N || ny<0 || ny>=N) { continue; }
// 이미 방문했거나 상어 크기보다 커도 continue
if(check[nx][ny]!=-1 || map[nx][ny]>shark_size) { continue; }
// (nx, ny)에 있는 물고기까지의 이동거리 갱신
check[nx][ny] = check[x][y] + 1;
// 먹을 수 있는 물고기라면
if(map[nx][ny]!=0 && map[nx][ny]<shark_size) {
// 이 과정은 맨 위, 맨 왼쪽 물고기부터 먹어야해서 검사하는 것
if(min_dist > check[nx][ny]) {
min_x = nx;
min_y = ny;
min_dist = check[nx][ny];
} else if(min_dist == check[nx][ny]) {
if(min_x == nx) {
if(min_y > ny) {
min_x = nx;
min_y = ny;
}
} else if(min_x > nx) {
min_x = nx;
min_y = ny;
}
}
}
// 다시 물고기 위치를 push
q.push({nx, ny});
}
}
}
int main() {
ios::sync_with_stdio(0);
int x, y;
cin >> N;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
cin >> map[i][j];
// 아기 상어의 위치를 알아내야 하기 때문
if(map[i][j] == 9) { shark_x=i; shark_y=j; map[i][j]=0; }
}
}
// 물고기 개수만큼 수행
while(1) {
min_dist = 400;
min_x = 20;
min_y = 20;
for(int i=0; i<N; i++) {
for(int j=0; j<N; j++) {
check[i][j] = -1;
}
}
// 여기까지 BFS를 위한 정보 초기화 과정
// 처음엔 아기상어 자리를 인자로 bfs 호출
bfs(shark_x, shark_y);
// 먹을 수 있는 물고기라면
if(min_x != 20 && min_y != 20) {
// 이동시간을 result에 더해주고
result += check[min_x][min_y];
// 얼마나 먹었는지 증가시켜주고
eat_cnt++;
// 아기상어가 성장할 수 있는 경우인지 검사
if(eat_cnt == shark_size) {
shark_size++;
eat_cnt = 0;
}
// 물고기를 먹었으니까 0으로 초기화
map[min_x][min_y] = 0;
// 상어의 위치를 재조정
shark_x = min_x;
shark_y = min_y;
} else {
// 먹을 수 있는 물고기가 없는 경우라면 break
break;
}
}
cout << result << '\n';
return 0;
}
내가 풀었다고 할 순 없지만,,
고민을 한참 해봤는데 아무리 손으로 그려봐도 해당 출력이 이해가 안돼서 문제를 마지막으로 다시 한 번 읽어보니까 계속 이상하게 읽고 있었다😠
결국 스터디 시간이 다 돼서 다른 분 코드의 도움을 받은 ㅠㅠㅠ
나중에 내 힘으로 다시 풀어봐야지
Author And Source
이 문제에 관하여([백준] 16236 아기 상어 C++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dbsrud11/백준-16236-C저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)