풀이일시 : 2021-02-10
문제 :
아기 상어가 성장해 청소년 상어가 되었다.
4×4크기의 공간이 있고, 크기가 1×1인 정사각형 칸으로 나누어져 있다. 공간의 각 칸은 (x, y)와 같이 표현하며, x는 행의 번호, y는 열의 번호이다. 한 칸에는 물고기가 한 마리 존재한다. 각 물고기는 번호와 방향을 가지고 있다. 번호는 1보다 크거나 같고, 16보다 작거나 같은 자연수이며, 두 물고기가 같은 번호를 갖는 경우는 없다. 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다.
오늘은 청소년 상어가 이 공간에 들어가 물고기를 먹으려고 한다. 청소년 상어는 (0, 0)에 있는 물고기를 먹고, (0, 0)에 들어가게 된다. 상어의 방향은 (0, 0)에 있던 물고기의 방향과 같다. 이후 물고기가 이동한다.
물고기는 번호가 작은 물고기부터 순서대로 이동한다. 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸, 이동할 수 없는 칸은 상어가 있거나, 공간의 경계를 넘는 칸이다. 각 물고기는 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기가 다른 물고기가 있는 칸으로 이동할 때는 서로의 위치를 바꾸는 방식으로 이동한다.
물고기의 이동이 모두 끝나면 상어가 이동한다. 상어는 방향에 있는 칸으로 이동할 수 있는데, 한 번에 여러 개의 칸을 이동할 수 있다. 상어가 물고기가 있는 칸으로 이동했다면, 그 칸에 있는 물고기를 먹고, 그 물고기의 방향을 가지게 된다. 이동하는 중에 지나가는 칸에 있는 물고기는 먹지 않는다. 물고기가 없는 칸으로는 이동할 수 없다. 상어가 이동할 수 있는 칸이 없으면 공간에서 벗어나 집으로 간다. 상어가 이동한 후에는 다시 물고기가 이동하며, 이후 이 과정이 계속해서 반복된다.
<그림 1>은 청소년 상어가 공간에 들어가기 전 초기 상태이다. 상어가 공간에 들어가면 (0, 0)에 있는 7번 물고기를 먹고, 상어의 방향은 ↘이 된다. <그림 2>는 상어가 들어간 직후의 상태를 나타낸다.
이제 물고기가 이동해야 한다. 1번 물고기의 방향은 ↗이다. ↗ 방향에는 칸이 있고, 15번 물고기가 들어있다. 물고기가 있는 칸으로 이동할 때는 그 칸에 있는 물고기와 위치를 서로 바꿔야 한다. 따라서, 1번 물고기가 이동을 마치면 <그림 3>과 같아진다.
2번 물고기의 방향은 ←인데, 그 방향에는 상어가 있으니 이동할 수 없다. 방향을 45도 반시계 회전을 하면 ↙가 되고, 이 칸에는 3번 물고기가 있다. 물고기가 있는 칸이니 서로 위치를 바꾸고, <그림 4>와 같아지게 된다.
3번 물고기의 방향은 ↑이고, 존재하지 않는 칸이다. 45도 반시계 회전을 한 방향 ↖도 존재하지 않으니, 다시 회전을 한다. ← 방향에는 상어가 있으니 또 회전을 해야 한다. ↙ 방향에는 2번 물고기가 있으니 서로의 위치를 교환하면 된다. 이런 식으로 모든 물고기가 이동하면 <그림 5>와 같아진다.
물고기가 모두 이동했으니 이제 상어가 이동할 순서이다. 상어의 방향은 ↘이고, 이동할 수 있는 칸은 12번 물고기가 있는 칸, 15번 물고기가 있는 칸, 8번 물고기가 있는 칸 중에 하나이다. 만약, 8번 물고기가 있는 칸으로 이동하면, <그림 6>과 같아지게 된다.
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구해보자.
입력 :
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 8보다 작거나 같은 자연수를 의미하고, 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗ 를 의미한다.
ex)
7 6 2 3 15 6 9 8
3 1 1 8 14 7 10 1
6 1 13 6 4 3 11 4
16 1 8 7 5 2 12 2
출력 :
상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 출력한다.
ex)
33
풀이 :
(사실 이 문제 풀이를 쓰기전에 19237번 풀이를 썼어야 했는데 몇시간을 풀어도 풀지 못해서 이 문제 풀이를 먼저한다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠ)
1. 기본적으로 DFS를 이용해 풀이.
- DFS를 쓴 이유는 상어가 먹이를 먹으러 이동하는 부분에서 방향이 주어져 있으나 몇 칸을 이동한다는게 없고 이를 랜덤으로 주어주고 먹을 수 있는 최대값을 찾아야 하기 때문에, copy map 을 주어주고 DFS를 반복하며 이의 최대값을 찾아야 했기 때문이다.
- back tracking 을 이용해 max가 아니면 다시 이전 값으로 되돌아오기 위해 값을 빼주는 과정을 수행할 수 있었지만, algorithm 의 max 함수를 사용하여 탐색하며 max 만 남겨두는 방법으로 수행하였다.
2. 구조체의 사용
- fish 구조체를 사용하여 fish의 x좌표 y좌표, 방향(dir), fish가 죽었는지의 여부를 저장해 줄 수 있었다.
3. 방향지시
- dx[]와 dy[]를 지정해주었다. 이의 방향은 [상] 부터 반시계방향으로 8방을 지정해주었다.
4. copymap과 copyfish 의 필요성
- DFS를 수행할 때마다 이의 입력 map은 copymap과 copyfish 가 들어간다. 만약 original map과 original fish 가 들어가게 된다면 매 DFS마다 map이 변경되어 다음 DFS 수행 시 다른 입력값이 들어갈 것이다. 동일한 입력을 위해 map과 fish를 copy 해주어 수행해준다.
5. 나머지연산의 사용
- 만약 현재 방향이 7이고 그곳에 상어가 있으면 방향을 우선순위에 따라 방향을 바꾸어 줘야 할 것이다. 이 때 방향을 8 9 10 11 12 13 ... 이 아닌 8 1 2 3 4 5 6 순으로 바꿔 줘야 한다. 따라서 나머지 연산을 사용해준다.
6. fish 간 위치를 바꿀 때 temp 의 사용
- fish가 비어있는 map 상으로 위치를 변경할 때에는 무작정 그 map으로 돌진해도 무리가 없다. 하지만 fish 가 존재하는 곳이라면 둘을 swap 해야 할 것이다. 이 때에 temp를 사용하여 swap 해주는 것은 swap 의 기본이다. (물론 temp 없이 swap하는 방법도 있지만..)
코드를 보며 주석을 따라가며 이해해보자.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef struct {
int x,y,dir;
int dead;
}fish;
//방향과 그 순서를 정의해주자. 상 부터 반시계방향으로 8방향 정의
const int dx[] = {-1,-1,0,1,1,1,0,-1};
const int dy[] = {0,-1,-1,-1,0,1,1,1};
void copymap(int a[4][4], int b[4][4]) {
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
a[i][j] = b[i][j];
}
}
return;
}
void copyfish(fish a[17], fish b[17]) {
for (int i = 0; i < 17; i++) {
a[i] = b[i];
}
}
int solution_dfs(int o_map[][4], int x, int y, int dir, fish o_fish[17]) {
//copy map 을 선언하고 copy를 수행해준다.
int map[4][4];
fish fish[17];
copymap(map, o_map);
copyfish(fish, o_fish);
//상어가 먹는 fish의 고유번호인 eat
int eat = map[x][y];
//먹힌 물고기가 가졌던 방향 이제는 상어가 가지는 방향
dir = fish[map[x][y]].dir;
fish[map[x][y]].x = -1;
fish[map[x][y]].y = -1;
fish[map[x][y]].dead = true;
map[x][y] = 0;
int answer = 0;
//fish의 이동은 1번부터 16번까지 순서대로 진행될 것이다.
for (int i = 1; i <= 16; i++) {
//죽지 않은 물고기에 대해서만 수행하면 될 것이다.
if (fish[i].dead == false) {
int nx = fish[i].x;
int ny = fish[i].y;
//8방향을 둘러보며 갈수있는 방향 지정
for (int j = 0; j < 8; j++) {
int cx = fish[i].x + dx[fish[i].dir];
int cy = fish[i].y + dy[fish[i].dir];
//상어가 있다면 방향 바꾸기 그리고 continue
if (cx == x && cy == y) {
fish[i].dir = (fish[i].dir+1) % 8;
continue;
}
//지정해준 좌표가 범위를 벗어난다면 방향바꾸고 continue
if (cx < 0 || cy < 0 || cx >= 4 || cy >= 4) {
fish[i].dir = (fish[i].dir+1) % 8;
continue;
}
//예외상황에 걸리지않고 방향을정한다면 nx와 ny를 갱신한다.
nx = cx;
ny = cy;
break;
}
//갈수있는 방향은 정했다. map에 그 좌표가 비었다면 fish를 옮겨준다.
if (map[nx][ny] == 0) {
map[fish[i].x][fish[i].y] = 0;
map[nx][ny] = i;
fish[i].x = nx;
fish[i].y = ny;
}
//map에 그 좌표에 fish가 존재한다면 swap 해준다.
else {
int tx, ty, temp;
tx = fish[i].x;
ty = fish[i].y;
fish[i].x = nx;
fish[i].y = ny;
fish[map[nx][ny]].x = tx;
fish[map[nx][ny]].y = ty;
map[tx][ty] = map[nx][ny];
map[nx][ny] = i;
}
}
}
//여기서 부터는 상어의 움직임이다.
int cx = x + dx[dir];
int cy = y + dy[dir];
//범위 벗어날때까지 이동
while (!(cy < 0 || cx < 0 || cy >= 4 || cx >= 4)) {
if (map[cx][cy] != 0) { //가는곳에 물고기가 있다면
//현재 map, cx, cy, fish 상태 넣어준다.
answer = max(answer, solution_dfs(map, cx, cy, dir, fish));
}
//갈수 있는 방향으로 더 넣어준다.
cx += dx[dir];
cy += dy[dir];
}
return answer + eat;
}
int main() {
int map[4][4] = { 0, };
fish fish[17];
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int a, b; //물고기와 그 방향
cin >> a >> b;
fish[a].x = i;
fish[a].y = j;
fish[a].dead = false;
fish[a].dir = b-1;
map[i][j] = a;
}
}
int result = solution_dfs(map, 0, 0, 0, fish);
printf("%d", result);
return 0;
}
'알고리즘 문제풀이 > 삼성역량테스트' 카테고리의 다른 글
| [삼성역량테스트] 2143 두 배열의 합 (0) | 2021.02.22 |
|---|---|
| [삼성역량테스트] 20061 모노미노도미노 2 (0) | 2021.02.13 |
| [삼성역량테스트] 19238 스타트택시 (0) | 2021.01.25 |
| [삼성역량테스트] 20055 컨베이어 벨트 위의 로봇 (0) | 2021.01.18 |
| [삼성역량테스트] 20056 마법사 상어와 파이어볼 (0) | 2021.01.17 |
댓글