[BFS&구현] 백준 16236 아기상어
2021. 3. 16. 11:57ㆍ알고리즘 문제분석
수행 시간: 3시간
글을 오랜만에 올리는 것 같다.. 요즘 취준때문에 바쁘기도하고 사실 알고리즘은 거의 매일 풀었는데 풀기만하고 올리지를 않아서 오늘 몰아서 올릴 것 같다.
친구와 타임어택으로 푼 골드4 수준의 삼성 SW 역량테스트 문제다. 문제자체는 크게 어려움을 느끼지 못했지만 생각해야될 부분도 많고 조건이 너무 많아서 코드를 짜는데 오래 걸렸다.
특히
if (time > (t + 1)) {
time = (t + 1);
f_x = nx;
f_y = ny;
}
else if (time == (t + 1)) {
if (f_x > nx) {
f_x = nx;
f_y = ny;
}
else if (f_x == nx && f_y > ny) {
f_y = ny;
}
}
이 부분에서 t 가아닌 t+1로 해줘야 된다는 사실은 친구가 내 코드를 봐준 후에야 알아차렸다..
이유는 for문 안에서 nx,ny(next x , next y)를 통해 구현되므로 현재 시간 t가 아닌 t+1로 해줘야했다.
#include <iostream>
#include <queue>
#include <string.h>
using namespace std;
int n;
int map[21][21];
bool visited[21][21] = { false, };
int shark = 2; //상어의 초기크기.
int shark_x, shark_y;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int min_dis, fish_x, fish_y;
int result = 0;
int eat = 0;
bool bfs(int x, int y) {
int cnt = 0;
int time = 10000;
int t;
int f_x, f_y;
queue <pair<pair<int, int>, int>> q;
q.push({ {x, y }, 0 });
while (!q.empty()) {
x = q.front().first.first;
y = q.front().first.second;
t = q.front().second;
//cout << x << " " << y << t << std::endl;
q.pop();
for (int i = 0;i < 4;i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < n) { //맵안에있고
if (visited[nx][ny] == false && map[nx][ny] <= shark) { // 방문하지 않고, 물고기의 크기가 상어보다 작거나 같으면
visited[nx][ny] = 1; // 이동거리 증가시킴
if (map[nx][ny] != 0 && map[nx][ny] < shark) { //먹을수 있다면?
if (time > (t + 1)) {
time = (t + 1);
f_x = nx;
f_y = ny;
}
else if (time == (t + 1)) {
if (f_x > nx) {
f_x = nx;
f_y = ny;
}
else if (f_x == nx && f_y > ny) {
f_y = ny;
}
}
}
q.push({ {nx,ny }, t + 1 }); //물고기 위치 push
}
}
}
}
if (time == 10000) {
return 0;
}
else {
shark_x = f_x;
shark_y = f_y;
map[shark_x][shark_y] = 0;
eat++;
if (shark == eat) {
shark++;
eat = 0;
}
result += time;
return 1;
}
}
int count_fish() {
int cnt = 0;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (map[i][j] > 0 && map[i][j] < shark) {
cnt++;
}
}
}
return cnt;
}
int sol() {
while (count_fish()) {
memset(visited, false, sizeof(visited));
if (!bfs(shark_x, shark_y))
break;
}
return result;
}
int main() {
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;
}
}
}
cout << sol();
}
'알고리즘 문제분석' 카테고리의 다른 글
[BFS] 백준 1697 숨바꼭질 (0) | 2021.03.16 |
---|---|
[구현] 백준 17144 미세먼지 안녕! (0) | 2021.03.16 |
[DP&DFS] 백준 1890 점프 (0) | 2021.03.08 |
[완전탐색] 백준 1051 숫자 정사각형 (0) | 2021.03.06 |
[구현] 백준 2564 경비원 (0) | 2021.03.06 |