💻 현생/⛓ 알고리즘
[백준] 16236번 : 아기 상어
영이오
2021. 5. 10. 19:53
문제
풀이
계속해서 상어를 이동시키며 이동할 때마다 bfs를 실행해야 한다.
다행히 입력 범위가 그렇게 크지 않아 bfs를 여러번 해도 시간 초과는 발생하지 않는다.
상어가 물고기를 먹는 우선순위 때문에 좀 헤맸다.
처음엔 단순히 '상-좌-우-하'의 순서로 탐색하면 되겠거니 했는데 '예제 입력 4'에서 틀린 답이 나왔다.
그래서 최단 경로에 위치한 모든 물고기들을 찾은 뒤, 그 물고기들 중에서 가장 우선순위가 높은 물고기를 찾는 방법으로 코드를 다시 작성했다.
소스코드
#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
vector<vector<int>> board;
int shark_size = 2; //상어의 크기
int fish_cnt, result; //먹은 물고기의 수, 이동하는데 걸린 총 시간
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) { //정렬
if (p1.first == p2.first)
return p1.second < p2.second;
return p1.first < p2.first;
}
pair<int, int> bfs(pair<int, int> shark) {
int size = board.size(), min_dist = 1000;
queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
dist.assign(size, vector<int>(size, -1));
vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보
dist[shark.first][shark.second] = 0;
q.push(shark);
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
(board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
dist[nr][nc] = dist[row][col] + 1; //거리 갱신
if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
min_dist = dist[nr][nc]; //최단 거리 갱신
}
if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
q.push(make_pair(nr, nc));
}
}
}
}
if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
return make_pair(-1, -1);
sort(candi.begin(), candi.end(), cmp); //정렬
fish_cnt++; //먹은 물고기의 수 증가
if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
fish_cnt = 0;
shark_size++;
}
board[candi[0].first][candi[0].second] = 9; //상어 이동
board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
result += min_dist; //활동 시간 증가
return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환
}
int main() {
int N;
pair<int, int> shark_pos;
cin >> N;
board.assign(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
if (board[i][j] == 9) //상어의 초기 위치
shark_pos = make_pair(i, j);
}
}
while ((shark_pos.first != -1) && (shark_pos.second != -1)) //상어가 더 이동할 수 없을 때까지 이동
shark_pos = bfs(shark_pos);
cout << result;
}전체 소스코드다.
vector<vector<int>> board;
int shark_size = 2; //상어의 크기
int fish_cnt, result; //먹은 물고기의 수, 이동하는데 걸린 총 시간
pair<int, int> dir[4] = {{-1, 0}, //상
{1, 0}, //하
{0, -1}, //좌
{0, 1}}; //우상어의 크기, 현재 먹은 물고기의 수, 활동 시간은 전역변수로 관리한다.
cin >> N;
board.assign(N, vector<int>(N));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> board[i][j];
if (board[i][j] == 9) //상어의 초기 위치
shark_pos = make_pair(i, j);
}
}board에 입력을 받으면서 상어의 초기 위치도 저장한다.
while ((shark_pos.first != -1) && (shark_pos.second != -1)) //상어가 더 이동할 수 없을 때까지 이동
shark_pos = bfs(shark_pos);그리고 상어의 위치를 계속 갱신할건데, bfs는 상어가 더이상 이동할 수 없을 때 (-1, -1)을 반환하도록 했다.
그러니 while문의 종료 조건도 (-1, -1)로 하면 된다.
pair<int, int> bfs(pair<int, int> shark) {
int size = board.size(), min_dist = 1000;
queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
dist.assign(size, vector<int>(size, -1));
vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보
dist[shark.first][shark.second] = 0;
q.push(shark);
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
(board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
dist[nr][nc] = dist[row][col] + 1; //거리 갱신
if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
min_dist = dist[nr][nc]; //최단 거리 갱신
}
if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
q.push(make_pair(nr, nc));
}
}
}
}
if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
return make_pair(-1, -1);
sort(candi.begin(), candi.end(), cmp); //정렬
fish_cnt++; //먹은 물고기의 수 증가
if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
fish_cnt = 0;
shark_size++;
}
board[candi[0].first][candi[0].second] = 9; //상어 이동
board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
result += min_dist; //활동 시간 증가
return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환
}bfs 함수는 먹을 수 있는 물고기의 좌표를 저장하는 부분과 물고기를 실제로 먹는 부분으로 나뉜다.
int size = board.size(), min_dist = 1000;
queue<pair<int, int>> q; //상어가 갈 수 있는 곳을 담은 큐
vector<vector<int>> dist; //상어의 방문 여부 및 이동 거리
dist.assign(size, vector<int>(size, -1));
vector<pair<int, int>> candi; //상어가 최종적으로 이동할 곳의 후보
dist[shark.first][shark.second] = 0;
q.push(shark);먼저 bfs에 기본적으로 필요한 큐와 거리를 저장하는 벡터를 선언했다.
그리고 최단거리에 있는 물고기들의 좌표를 저장할 candi 벡터와 그 최단거리를 저장할 min_dist 변수도 선언했다.
상어의 처음 위치의 dist를 0으로 초기화 하고 그 위치를 큐에 넣으며 시작한다.
while (!q.empty()) {
int row = q.front().first;
int col = q.front().second;
q.pop();
if (dist[row][col] < min_dist) { //dist[row][col]이 min_dist 이상이라면, 물고기가 있어도 최단거리가 아님
for (int i = 0; i < 4; i++) {
int nr = row + dir[i].first;
int nc = col + dir[i].second;
if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
(board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
dist[nr][nc] = dist[row][col] + 1; //거리 갱신
if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
min_dist = dist[nr][nc]; //최단 거리 갱신
}
if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
q.push(make_pair(nr, nc));
}
}
}
}특정 좌표의 상하좌우는 그 좌표의 dist값이 min_dist보다 작을 때만 탐색한다.
왜냐하면 특정 좌표에서 상하좌우로 이동하면 무조건 1이 더해질텐데 dist값이 이미 min_dist보다 같거나 컸다면 새롭게 이동한 좌표는 절대 최단 거리에 존재하는 물고기가 될 수 없기 때문이다.
if ((nr >= 0) && (nr < size) && (nc >= 0) && (nc < size) && (dist[nr][nc] == -1) && //범위 내에 있는 미방문 좌표
(board[nr][nc] <= shark_size)) { //상어가 갈 수 있다면
dist[nr][nc] = dist[row][col] + 1; //거리 갱신
if ((board[nr][nc] > 0) && (board[nr][nc] < shark_size)) { //상어가 먹을 수 있는 물고기라면
candi.push_back(make_pair(nr, nc)); //최종 이동 후보에 넣음
min_dist = dist[nr][nc]; //최단 거리 갱신
}
if (dist[nr][nc] < min_dist) //먹을 수 있는 물고기를 찾았다면 더 나갈 필요 없음
q.push(make_pair(nr, nc));
}갈 수 있는 좌표를 계속 탐색하며 큐에 넣어준다.
그러다가 만약 해당 좌표에 먹을 수 있는 물고기가 있다면 min_dist를 갱신하고 그 좌표를 candi 벡터에 넣어준다.
bfs 탐색이기 때문에 처음으로 찾은 물고기의 dist가 min_dist가 될 수 있다.
if (candi.empty()) //후보 배열이 비어있다면 상어가 이동할 수 없는 것
return make_pair(-1, -1);
sort(candi.begin(), candi.end(), cmp); //정렬
fish_cnt++; //먹은 물고기의 수 증가
if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
fish_cnt = 0;
shark_size++;
}
board[candi[0].first][candi[0].second] = 9; //상어 이동
board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
result += min_dist; //활동 시간 증가
return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환while문이 종료되면 candi 벡터에 값이 있는지 확인한다.
만약 값이 없다면 먹을 수 있는 물고기가 없다는 뜻이고 상어가 더이상 이동할 수 없다는 뜻이니 (-1, -1)을 리턴한다.
그렇지 않다면 candi 벡터를 정렬한다.
bool cmp(const pair<int, int> &p1, const pair<int, int> &p2) { //정렬
if (p1.first == p2.first)
return p1.second < p2.second;
return p1.first < p2.first;
}이렇게하면 조건에 맞는 물고기의 좌표가 맨 앞으로 온다.
fish_cnt++; //먹은 물고기의 수 증가
if (fish_cnt == shark_size) { //먹은 물고기의 수가 상어의 크기와 같다면
fish_cnt = 0;
shark_size++;
}
board[candi[0].first][candi[0].second] = 9; //상어 이동
board[shark.first][shark.second] = 0; //상어의 원래 위치 0으로 변경
result += min_dist; //활동 시간 증가
return make_pair(candi[0].first, candi[0].second); //상어의 새로운 위치 반환물고기를 먹어야 하니 fish_cnt를 하나 늘려준다.
근데 만약 이 fish_cnt가 shark_size와 같다면 상어의 크기가 커질 수 있으니 그럴 경우 shark_size를 늘려주고 fist_cnt는 다시 0으로 초기화 한다.
그리고 상어의 새로운 위치를 board 벡터에 반영하고 min_dist를 result에 더해준다.
마지막으로 상어의 새로운 위치를 리턴하면 된다.