문제 링크 : https://www.acmicpc.net/problem/16236
삼성 SW 코딩테스트에 출제됐던 문제다.
문제 풀이를 따지기 전에, 먼저 굵직한 로직은 다음과 같다.
(1) 현재 상어의 위치를 전역 변수로 저장하고, 상어의 위치에 있던 '9'는 '0'으로 변경한다.
(2) while문을 세워서 상어가 물고기를 한 마리라도 먹을 수 없을때까지 while문의 roop를 진행한다.
(2)-(2) 이때 while문 내부에 bool문형 bfs함수를 세운다. bfs함수는 먹을 수 있는 물고기가 있으면 true를 반환하고, 아니면 false를 반환한다.
(3) 모든 while문을 최종적으로 빠져나오면 정답을 출력한다.
문제 풀이는 다음과 같다.
1. 먼저 전역으로 선언한 변수들은 다음과 같다.
int n,ate,s=2,y,x,nm,ny,nx,my[]={1,0,-1,0},mx[]={0,1,0,-1},ans=0,arr[21][21];
bool ch[21][21];
typedef pair<int,pair<int,int>> fish;
typedef pair<int,pair<int,int>> shark;ate는 여탯껏 먹은 상어의 물고기 수. 만약 ate가 s와 같다면 s는 +1 해주고 ate는 다시 0으로 초기화해준다.
y,x는 상어의 현재 위치. 이 위치는 물고기를 먹을때마다 갱신된다.
fish는 먹은 물고기의 정보를 저장하는 구조체이고, shark는 물고기를 먹기위해 움직이는 shark의 정보를 저장하는 구조체다.
각각 첫 번째 int는 움직임 횟수, 두 번째 세 번째 int는 위치값을 나타낸다.
2. n의 값을 입력받고 배열에 값을 저장한다.
cin >> n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> arr[i][j];
if(arr[i][j]==9){
y=i;
x=j;
arr[i][j] = 0; // 중요
}
}
}이때 유의사항이, 상어의 위치값을 별도로 저장할때 반드시 상어의 위치에 있던 9는 0으로 바꿔야 한다는 점이다.
3. 물고기를 한 마리라도 먹을 수 없을때까지 while문을 진행한다.
while(true){ // 먹을 수 있는 물고기중 가장 최단거리 물고기를 판단해서 잡아먹는다.
if(!bfs()) break;
}
4. 다음은 bfs코드의 내부이다 먼저 굵직하게 코드 전체를 훑고 하나씩 이해해보자.
bool bfs(){
queue<shark> q;
vector<fish> v;
int info[] = {500,500,500};
q.push({0,{y,x}});
ch[y][x] = true;
while(!q.empty()){
int mm = q.front().first;
int yy = q.front().second.first;
int xx = q.front().second.second;
q.pop();
for(int i=0; i<4; i++){
nm = mm +1;
ny = yy+my[i];
nx = xx+mx[i];
if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&arr[ny][nx]<=s){ // 조건 중요
ch[ny][nx] = true;
q.push({nm,{ny,nx}});
if(arr[ny][nx]>0&&arr[ny][nx]<s) v.push_back({nm,{ny,nx}});
}
}
}
if(v.size()==0) return false;
else{
sort(v.begin(),v.end());
for(int i=0; i<v.size(); i++){
if(v[i].first<info[0]){ // 보다 단거리에 있다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(v[i].first==info[0]){ // 거리가 같다면
if(info[1]<v[i].second.first) continue;
else if(info[1]>v[i].second.first){ // y축이 더 위쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(info[1]==v[i].second.first){ // 만약 y축마져도 같다면
if(info[2]>v[i].second.second){ // x축이 더 왼쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
}
}
}
ans += info[0];
arr[info[1]][info[2]] = 0;
y = info[1];
x = info[2];
ate++;
if(ate==s){
s++;
ate = 0;
}
memset(ch,false,sizeof(ch)); // 막판에 방문여부 초기화 잊지말기
return true;
}
}
5. 먼저 bfs코드의 상단 부분은 다음과 같다.
queue<shark> q; // 1
vector<fish> v; // 2
int info[] = {500,500,500}; // 3
q.push({0,{y,x}}); // 4
ch[y][x] = true;
while(!q.empty()){ // 5
int mm = q.front().first;
int yy = q.front().second.first;
int xx = q.front().second.second;
q.pop();
for(int i=0; i<4; i++){ // 6
nm = mm +1;
ny = yy+my[i];
nx = xx+mx[i];
if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&arr[ny][nx]<=s){ // 7 조건 중요
ch[ny][nx] = true;
q.push({nm,{ny,nx}});
if(arr[ny][nx]>0&&arr[ny][nx]<s) v.push_back({nm,{ny,nx}}); // 8
}
}
}(1) q는 상어의 위치를 저장하는 큐이다. shark는 typedef<pair<int,pair<int,int>>로 지정되어있다.
(2) v는 상어가 움직이면서 먹을 수 있는 물고기의 정보를 저장한 벡터이다. fish는 상어와 동일한 구조체로 저장되어있다.
(3) info는 최종적으로 먹게된 가장 최단거리의 물고기 정보를 저장한 배열이다. 초기값은 20*20보다 큰 수 중 적당히 가장 큰 값을 넣어주면 된다.
(4) 큐에 현재 상어의 움직임 수와 위치를 저장해주고, 해당 위치를 방문표시해준다.
(5) 큐의 front정보를 새로 저장해주고 pop해준다.
(6) 4방위 판별하여 갈 수 있는 위치를 찾아본다.
(7) 만약 해당 위치가 배열의 범위를 넘어서지 않고, 방문한 적이 없으며, 동시에 해당 배열의 값이 현재 상어의 사이즈보다 작을 경우, 방문 표시를 해준 뒤 큐에 누적 움직임 횟수와 해당 위치값을 저장해준다.
(8) 동시에 해당 위치의 물고기 크기가 0보다 크고 상어의 사이즈보다 작을 경우, v 벡터에 해당 물고기의 정보(물고기까지 움직임 횟수, 물고기의 위치)를 저장해준다.
6. 아래는 bfs코드의 하단 부분이다.
if(v.size()==0) return false; // 1
else{
for(int i=0; i<v.size(); i++){
if(v[i].first<info[0]){ //2 -> 보다 단거리에 있다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(v[i].first==info[0]){ // 3 -> 거리가 같다면
if(info[1]<v[i].second.first) continue; // 4
else if(info[1]>v[i].second.first){ // 5 -> y축이 더 위쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(info[1]==v[i].second.first){ // 6 -> 만약 y축마져도 같다면
if(info[2]>v[i].second.second){ // 7 - x축이 더 왼쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
}
}
}
ans += info[0]; // 8
arr[info[1]][info[2]] = 0;
y = info[1];
x = info[2];
ate++; // 9
if(ate==s){
s++;
ate = 0;
}
memset(ch,false,sizeof(ch)); // 10 막판에 방문여부 초기화 잊지말기
return true; // 11
}(1) 만약 v의 사이즈가 0이라면 먹은 물고기가 없다는 뜻이다. false를 반환하면 된다.
(2) 만약 먹은 물고기의 사이즈가 0보다 크다면 for문을 진행해준다.
[i]번째 물고기의 거리가 현재 저장된 먹은 물고기의 거리보다 짧다면 [i]번째 물고기 정보를 갱신해준다.
(3) 거리가 같을 경우,
(4) 만약 [i]번째 물고기의 y값이 현재 저장된 물고기의 y값보다 크다면 continue로 진행한다.
(5) 반대로 [i]번째 물고기가 더 위에 있다면 [i]번째 물고기 정보를 갱신해준다.
(6) 만약 y축마저 값이 같다면 x축으로 값을 비교해야한다.
(7) [i]번째 물고기의 x축이 보다 0에 가깝다면 [i]번째 물고기 정보를 갱신해주면 된다.
(8) 최종적으로 저장된 물고기에게 가기위해 움직인 거리를 ans에 더해준다.
동시에 해당 물고기의 위치값에 0을 저장해주고, 상어의 위치 또한 잡아먹은 물고기의 위치로 갱신해준다.
(9) ate의 값을 +1 해주는데, 만약 ate가 s와 같아진다면 s의 크기를 +1해주고 ate는 0으로 저장해준다.
(10) 여탯껏 방문했던 bool문 ch를 false로 초기화해주고
(11) true를 반환한다.
7. while문을 종료하고 ans를 출력한다.
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
int n,ate,s=2,y,x,nm,ny,nx,my[]={1,0,-1,0},mx[]={0,1,0,-1},ans=0,arr[21][21];
bool ch[21][21];
typedef pair<int,pair<int,int>> fish;
typedef pair<int,pair<int,int>> shark;
bool bfs(){
queue<shark> q;
vector<fish> v;
int info[] = {500,500,500};
q.push({0,{y,x}});
ch[y][x] = true;
while(!q.empty()){
int mm = q.front().first;
int yy = q.front().second.first;
int xx = q.front().second.second;
q.pop();
for(int i=0; i<4; i++){
nm = mm +1;
ny = yy+my[i];
nx = xx+mx[i];
if(ny>=1&&ny<=n&&nx>=1&&nx<=n&&!ch[ny][nx]&&arr[ny][nx]<=s){ // 조건 중요
ch[ny][nx] = true;
q.push({nm,{ny,nx}});
if(arr[ny][nx]>0&&arr[ny][nx]<s) v.push_back({nm,{ny,nx}});
}
}
}
if(v.size()==0) return false;
else{
for(int i=0; i<v.size(); i++){
if(v[i].first<info[0]){ // 보다 단거리에 있다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(v[i].first==info[0]){ // 거리가 같다면
if(info[1]<v[i].second.first) continue;
else if(info[1]>v[i].second.first){ // y축이 더 위쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
else if(info[1]==v[i].second.first){ // 만약 y축마져도 같다면
if(info[2]>v[i].second.second){ // x축이 더 왼쪽에 있는걸로 갱신해준다
info[0] = v[i].first;
info[1] = v[i].second.first;
info[2] = v[i].second.second;
}
}
}
}
ans += info[0];
arr[info[1]][info[2]] = 0;
y = info[1];
x = info[2];
ate++;
if(ate==s){
s++;
ate = 0;
}
memset(ch,false,sizeof(ch)); // 막판에 방문여부 초기화 잊지말기
return true;
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cin >> arr[i][j];
if(arr[i][j]==9){
y=i;
x=j;
arr[i][j] = 0; // 중요
}
}
}
while(true){ // 먹을 수 있는 물고기중 가장 최단거리 물고기를 판단해서 잡아먹는다.
if(!bfs()) break;
}
cout << ans << "\n";
return 0;
}
'🖥️ CS > Baekjoon Algorithms' 카테고리의 다른 글
| 백준 6087번 레이저통신 (C++) (0) | 2021.06.01 |
|---|---|
| 백준 16973번 직사각형 탈출 (C++) (0) | 2021.05.31 |
| 백준 16954번 움직이는 미로 탈출 (C++) (0) | 2021.05.25 |
| LeetCode 322. Coin Change (0) | 2021.05.24 |
| 백준 16933번 벽 부수고 이동하기3 - Structure (C++) (0) | 2021.05.24 |