## SW 역량테스트 - [백준] 아기 상어 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

### SW 역량테스트 - [백준] 아기 상어 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:47

## SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

### 해답 코드 :

``````#include <iostream>
#include <deque>

using namespace std;

typedef struct pos {

int row;
int col;

}pos;

typedef struct route {

int row;
int col;
int dist;

} route;

typedef struct shark {

int row;
int col;
int s_size;
int feed;

}shark;

int N;
int map[20][20];

shark baby;
int ans_sec;

int dR[4] = {-1, 1, 0, 0};
int dC[4] = {0, 0, -1, 1};

deque<pos> food;

void eat(pos fish) {

baby.feed++;

if (baby.feed == baby.s_size) {

if (baby.s_size < 8) baby.s_size++;
baby.feed = 0;
}

// empty original position
map[baby.row][baby.col] = 0;

// move
map[fish.row][fish.col] = 9;
baby.row = fish.row;
baby.col = fish.col;
}

bool isRange(int row, int col) {
if (row < 0 || row >= N || col < 0 || col >= N) {
return false;
}
else {
return true;
}
}

// prioritize "Up" and "Left"
route prior_pos(route A, route B) {

if (A.row < B.row) {
return A;
}
else if (A.row == B.row && A.col < B.col) {
return A;
}
else {
return B;
}

}

// return minimum distance from st to end
route bfs_dist(pos st) {

route t_pos;
route n_pos;
bool visited[20][20] = { false };

int n_r, n_c;
deque<route> myQ;
int min_dist = 99999;

// compare route with same distance
deque<route> prior_q;

t_pos = { st.row, st.col, 0 };
visited[t_pos.row][t_pos.col] = true;
myQ.push_front(t_pos);

while (!myQ.empty()) {

// visit
t_pos = myQ[0];
if (t_pos.dist > min_dist) {
break;
}

// terminator
if (map[t_pos.row][t_pos.col] < baby.s_size && map[t_pos.row][t_pos.col] != 0) {
min_dist = t_pos.dist;
prior_q.push_back(t_pos);
myQ.pop_front();
continue;
}

for (int i = 0; i < 4; i++) {

n_r = t_pos.row + dR[i];
n_c = t_pos.col + dC[i];

// check move condition
if (isRange(n_r, n_c) && !visited[n_r][n_c] && map[n_r][n_c] <= baby.s_size) {
n_pos = {n_r, n_c, t_pos.dist+1};
visited[n_r][n_c] = true;
myQ.push_back(n_pos);
}
}

myQ.pop_front();
}

if (!prior_q.empty()) {
t_pos = prior_q[0];

for (int i = 0; i < prior_q.size(); i++) {
t_pos = prior_pos(t_pos, prior_q[i]);
}

return t_pos;
}

// if there is no route
t_pos = {-1, -1, 99999};
return t_pos;
}

// check three cases
int shark_move() {

route min_route;

pos start = {baby.row, baby.col};
pos target;

// push possible fish to the food vector
min_route = bfs_dist(start);

if (min_route.dist >= 99999) {
return -1;
}
else {
target = {min_route.row, min_route.col};
eat(target);
ans_sec += min_route.dist;

return 1;
}

}

int main() {

cin >> N;

ans_sec = 0;

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {

cin >> map[i][j];

if (map[i][j] == 9) {
baby = {i, j, 2, 0};
}

}
}

while (shark_move() != -1) {
;
}

cout << ans_sec << endl;

}``````

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제

#### 'Data Structures, Algorithm > SW 역량테스트' 카테고리의 다른 글

 SW 역량테스트 - [백준] 낚시왕 문제 풀이/해답/코드 (C++ / JAVA)  (0) 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15 2020.10.15