풀이 소요시간 : 약 60분
요즘 삼성 SW 역량테스트 마법사 상어 시리즈를 풀고있는데, 폼이 나쁘지 않다. 이전보다 구현력이 많이 올라간거같아서 기분이 좋지만, 이번 아기상어 풀이과정은 실전이였다면 아찔한 치명적 실수 하나를 포함했다.
번외로 요즘 프로그래머스만 주구장창 풀어서 부진했던 백준 티어가 골드 2로 올라갔다.
사실 별 의미는 없다. (다시 프로그래머스 풀어야지)
그래서 무엇이 문제였는가?
우선 시뮬레이션 구현 과정에 있어서
먹을 수 있는 물고기의 좌표를 구하는 과정과 해당 좌표까지의 거리를 구하는 과정을 분리했다. 사실 이것은 나쁘지 않다. 좌표를 구하면서 BFS 까지 한번에 돌리려면 구현이 지저분해질 수 있기 때문이다. 다만 해당 좌표까지 먹을 수 없는 물고기에 둘러쌓여서 도달할 수 없는 경우를 아예 생각하지 못했다는 것이다.
따라서 테스트 케이스는 모두 환상적으로 통과했지만 제출을 하면 오답처리가 뜨는 기가막히는 상황이 발생했다.
왜 생각 못했을까?
우선 문제에 벽 의 개념이 없다. 물론 아기상어보다 큰 물고기가 있는 칸을 건너지는 못하지만 이것을 벽의 개념으로 생각하지 못한듯 하다. 다음부터는 주의하도록 하자.
나름의 요령?
void Input() {
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> Map[i][j];
if (Map[i][j] == 9)
{
shark_X = i;
shark_Y = j;
//상어는 좌표로만 표기
Map[i][j] = 0;
}
}
}
}위처럼 아기 상어의 좌표를 받는 순간 해당 좌표를 9 가 아닌 0 으로 만들어버렸다.
9라는 값은 신경써야 할 예외처리가 많고 딱히 의미가 있는 값이 아니기 때문에 자의적으로 처리한 부분이다.
전체 코드
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int N;
int Map[100][100];
int Visit[100][100];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
int shark_X;
int shark_Y;
int shark_Size = 2;
struct Fish {
int x;
int y;
int m;
int dist;
};
vector<Fish> Eat; // 먹을 수 있는 물고기 좌표 + 거리(추가)
vector<pair<int, int>> Position; // 먹을 수 있는 물고기 좌표
// 거리 -> x축 -> y축 순서대로 정렬
bool Cmp(Fish& A, Fish& B) {
if (A.dist == B.dist)
{
if (A.x == B.x)
{
return A.y < B.y;
}
return A.x < B.x;
}
return A.dist < B.dist;
}
void Input() {
cin >> N;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
cin >> Map[i][j];
if (Map[i][j] == 9)
{
shark_X = i;
shark_Y = j;
//상어는 좌표로만 표기
Map[i][j] = 0;
}
}
}
}
bool Check_Fish() {
int Cnt = 0;
for (int i = 1; i <= N; i++)
{
for (int j = 1; j <= N; j++)
{
if (Map[i][j] >= shark_Size || Map[i][j] == 0) continue; //상어가 못먹는 사이즈 or 빈칸 or 아기상어의 초기 위치
if (i == shark_X && j == shark_Y) continue; //상어의 좌표 X
Cnt++;
Position.push_back({ i, j }); //먹을 수 있는 물고기의 좌표 추가
}
}
if (Cnt == 0) return false;
else return true;
}
//목표 상어까지의 좌표 + 최단거리(Fish) 정보 저장을 목적
void Bfs(int Gx, int Gy) {
queue<pair<pair<int, int>, int>> Q; // x좌표, y좌표, 시간
Q.push({ {shark_X, shark_Y}, 0 }); //아기상어의 좌표, 시간 삽입
Visit[shark_X][shark_Y] = 1; //방문 체크
while (!Q.empty())
{
int px = Q.front().first.first;
int py = Q.front().first.second;
int time = Q.front().second;
Q.pop();
if (px == Gx && py == Gy) //목표 물고기까지 도달
{
Eat.push_back({ Gx, Gy, Map[Gx][Gy], time });
break;
}
for (int i = 0; i < 4; i++)
{
int nx = px + dx[i];
int ny = py + dy[i];
if (nx < 1 || ny < 1 || nx > N || ny > N) continue; //범위를 벗어남
if (Visit[nx][ny] == 1) continue; //이미 방문
if (Map[nx][ny] > shark_Size) continue; //아기상어보다 큰 물고기가 있는 칸은 못지나감
Visit[nx][ny] = 1;
Q.push({ {nx, ny}, time + 1 });
}
}
memset(Visit, 0, sizeof(Visit));
//방문 배열 초기화
}
void Clear() {
Position.clear();
Eat.clear();
}
int main() {
Input();
int Time = 0;
int Count_For_Next = shark_Size;
//다음 크기가 되기위한 목표 물고기 : 초기 값 2
while (true)
{
//더이상 잡아먹을 물고기가 없다.
if (Check_Fish() == false)
{
cout << Time << '\n';
break;
}
//있다면 Position 에 좌표가 저장된 상태
for (auto E : Position)
{
int px = E.first;
int py = E.second;
Bfs(px, py); //목표 좌표
}
if (Eat.size() == 0)
{
cout << Time << '\n';
break;
}
//Eat 에 물고기 정보 저장 완료 : 위치 정렬 (거리 -> x축 -> y축)
sort(Eat.begin(), Eat.end(), Cmp);
int x = Eat[0].x;
int y = Eat[0].y;
Map[x][y] = 0; //해당 칸은 빈칸이 된다.
Time += Eat[0].dist; //해당 칸까지 이동하는데 소요된 시간 추가.
Count_For_Next--; //다음 사이즈까지 필요로 하는 물고기 카운트 감소.
//아기상어의 위치 이동
shark_X = x;
shark_Y = y;
if (Count_For_Next == 0) //다음 사이즈가 됨
{
shark_Size++;
Count_For_Next = shark_Size;
}
Clear();
}
}
SSAFY 11th