#include <stdio.h>
#include <queue>
using namespace std;
int a[26][26];
int ch[26][26];
struct Pos
{
int x;
int y;
int dis;
Pos(int x, int y, int z)
{
this -> x = x;
this -> y = y;
this -> dis = z;
}
bool operator<(const Pos &a) const
{
if(dis == a.dis)
{
if(x == a.x) return y > a.y;
else
return x > a.x;
}
else return dis > a.dis;
}
};
struct Simba
{
int x;
int y;
int size;
int cnt;
void SizeUp()
{
cnt = 0;
size++;
}
};
int main()
{
int n, res = 0;
scanf("%d", &n);
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
priority_queue<Pos> pQ;
Simba simba;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
if(a[i][j] == 9)
{
simba.x = i;
simba.y = j;
a[i][j] = 0;
}
}
}
pQ.push(Pos(simba.x, simba.y, 0));
simba.size = 2;
simba.cnt = 0;
while(!pQ.empty())
{
Pos temp = pQ.top();
pQ.pop();
int x = temp.x;
int y = temp.y;
int dis = temp.dis;
if(a[x][y] != 0 && a[x][y] < simba.size)
{
a[x][y] = 0;
simba.x = x;
simba.y = y;
simba.cnt++;
if(simba.cnt == simba.size)
simba.SizeUp();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
ch[i][j] = 0;
}
}
while(!pQ.empty()) pQ.pop();
res = dis;
}
for(int i = 0; i < 4; i++)
{
if(x+dx[i] < 1 || x+dx[i] > n || y+dy[i] < 1 || y+dy[i] > n || a[x+dx[i]][y+dy[i]] > simba.size || ch[x+dx[i]][y+dy[i]] > 0) continue;
ch[x+dx[i]][y+dy[i]] = 1;
pQ.push(Pos(x+dx[i], y+dy[i], dis+1));
}
}
printf("%d", res);
return 0;
}1. 토끼의 위치를 우선순위큐에 저장해서 가장 가까우면서, 가장 위쪽이면서, 가장 왼쪽인 토끼를 잡아먹을 수 있게 심바를 이동시켜야한다. 이는 아래와 같이 표현할 수 있다.
struct Pos
{
int x;
int y;
int dis;
Pos(int x, int y, int z)
{
this -> x = x;
this -> y = y;
this -> dis = z;
}
bool operator<(const Pos &a) const
{
if(dis == a.dis)
{
if(x == a.x) return y > a.y;
else
return x > a.x;
}
else return dis > a.dis;
}
};연산자 오버로딩을 통해서 우선순위큐로 들어가면 위와 같이 표현할시에 최소힙으로 들어간다.
즉
if (비교 대상 거리 == 입력 대상 거리) 가 참이라면
if (비교 대상 행의 위치 == 입력 대상 행의 위치) 가 참이라면 입력 대상 열의 위치를 비교 대상 열의 위치보다 작게
거짓이라면 입력 대상 행의 위치를 비교 대상 행의 위치보다 작게
if (비교 대상 거리 == 입력 대상 거리) 가 거짓이라면 입력 대상 거리가 비교 대상 거리보다 작게
이렇게 하면
2마리 이상이면 가장 가까운 토끼 먹기
- 가장 위쪽 // 가장 왼쪽
조건을 만족할 수 있게 된다.
2. 심바의 위치, 크기, 먹은 토끼의 수를 Simba 라는 구조체의 멤버 변수로 지정하고 Simba 형태의 simba를 생성한다.
struct Simba
{
int x;
int y;
int size;
int cnt;
void SizeUp()
{
cnt = 0;
size++;
}
};
int main()
{
Simba simba;
}이 때 생성자로 생성할 필요는 없다.
3. 입력이 9라면 심바의 위치로 생각하고 현재 심바의 위치를 i행 j열로 두고, 그 자리를 0으로 초기화해준다. 나중에 지나갈 수도 있는 길이기 때문이다. (9로 해두면 크기가 9인 토끼가 있는 것으로 간주되어버린다)
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
scanf("%d", &a[i][j]);
if(a[i][j] == 9)
{
simba.x = i;
simba.y = j;
a[i][j] = 0;
}
}
}
4. 먼저 우선순위큐에서 값을 빼온다. 그 값은 심바의 위치가 아닌 토끼의 위치로 간주한다. 그 이유는 6번에서 나온다. 그 값이 0이 아니고 심바보다 사이즈가 작다면 (사이즈가 0이 아닌 심바보다 작은 토끼) 그 토끼를 먹고 그 자리를 차지한다. 이후 심바가 이동했던 길을 체크하는 ch 배열을 모두 0으로 초기화해준다. 그 이유도 6번에서 나온다.
5. 결과값 res = dis 로 해주는데, 이는 지금까지 심바가 이동한 거리이다. 계속해서 Pos(x, y, z) 로 z를 통해서 넘겨주기 때문이다. 또한 우선순위큐를 모두 비워줘야하는데 이 이유도 6번에서 나온다.
Pos temp = pQ.top();
pQ.pop();
int x = temp.x;
int y = temp.y;
int dis = temp.dis;
if(a[x][y] != 0 && a[x][y] < simba.size)
{
a[x][y] = 0;
simba.x = x;
simba.y = y;
simba.cnt++;
if(simba.cnt == simba.size)
simba.SizeUp();
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
ch[i][j] = 0;
}
}
while(!pQ.empty()) pQ.pop();
res = dis;
}
6. 이유
- 토끼의 위치로 간주하는 이유 : 만약 첫 if 문 사이즈가 작은 토끼인지 아닌지의 조건을 만족하지 않는다면 아래 for문으로 들어오게 된다.
for(int i = 0; i < 4; i++)
{
if(x+dx[i] < 1 || x+dx[i] > n || y+dy[i] < 1 || y+dy[i] > n || a[x+dx[i]][y+dy[i]] > simba.size || ch[x+dx[i]][y+dy[i]] > 0) continue;
ch[x+dx[i]][y+dy[i]] = 1;
pQ.push(Pos(x+dx[i], y+dy[i], dis+1));
}상, 하, 좌, 우 4방향을 모두 확인해서 n*n을 벗어나지 않고, 심바보다 사이즈가 작으며, 이미 이동한 길이 아니라면
이동한 길을 1로 체크하고 우선순위큐에 넣는다. 이 우선순위큐에 넣는 행위 때문에 토끼의 위치로 간주하는 것이다. 왜냐하면 다음 while에서 심바가 이동한 것으로 간주하기 때문이다.
- 토끼를 먹고나면 ch배열을 초기화하는 이유 : 위와 같이 토끼를 먹지 못했다면 가장 가까운 토끼까지 이동하기 위해 최단거리를 알기 위해서 ch배열을 쓴다. 근데 토끼를 먹었다? 그렇다면 다시 다음 최단거리의 토끼를 알아야하기 때문에 ch를 초기화해주어야한다.
- 우선순위큐를 모두 비워주는 이유 : 위 코드에서는 for 문을 i가 3이 될 때까지 돈다. 즉 상, 하, 좌, 우 4방향 중에 조건을 만족하는 모든 방향이 우선순위큐에 들어가게 된다. 그 중에서 가장 가깝고, 위쪽이면서, 왼쪽인 것만을 찾아서 이동해야하기 때문에 그것을 제외한 우선순위큐에 있는 값은 전부 빼주어야한다.
