문제 링크
www.acmicpc.net/problem/19236
19236번: 청소년 상어
첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는
www.acmicpc.net
접근 방법
바보같은 실수 하나로 오랜 시간을 잡아먹은 문제다.
필자가 했던 실수는 물고기를 이동시키지 않은 상태에서 상어가 먹을 수 있는 물고기가 있는지 확인하고 물고기를 이동시켰다는 점이다. 이렇게 구현을 한 상태에서 문제에서 주어진 테스트 케이스가 모두 맞아 떨어져 오류를 수정하기 힘들었다.
문제 풀이는 단순하다.
1. 상어를 0,0에 배치시키고 상태를 업데이트 한다.
2. DFS를 실행하는데 현재 4X4의 물고기들 상태를 저장해 두고 물고기를 이동시킨다.
3. 상어가 먹을 수 있는 먹이가 있는지 확인한다.
4. 먹을 수 있다면 DFS를 진행 시키고 아니면 최대 값을 갱신하고 저장 해 둔 상태로 다시 복원한다.
물고기를 이동시키는 함수를 풀이하자면
1. 맵을 스캔하며 n번 물고기의 좌표를 vector<pair<int, int>> fishInfo에 저장한다.
void moveAll(info &shark) {
vector<pair<int, int>> fishInfo(17, {-1,-1}); //n번 물고기와 좌표를 매핑
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (!(i == shark.x && j == shark.y))
if (map[i][j].num != 0)
fishInfo[map[i][j].num] = { i,j };
for (int i = 1; i < 17; i++)
if (fishInfo[i].first != -1)
move(fishInfo, shark, i);
}
2. fishInfo를 1번 부터 탐색하며 한 마리 씩 이동시킨다. 이 때 물고기가 이동하며 swap되는 정보가 fishInfo에 실시간으로 갱신되야 하므로 move()함수에 fishInfo를 참조 연산자로 넘겨주었다.
void move(vector<pair<int, int>> &fishInfo, info shark, int num) {
int x = fishInfo[num].first;
int y = fishInfo[num].second;
int dir = map[x][y].dir;
for (int i = 0; i < 8; i++) {
int next_dir = (dir + i) % 8;
int next_x = x + direction[next_dir].first;
int next_y = y + direction[next_dir].second;
if (inRange(next_x, next_y) && !(next_x == shark.x && next_y == shark.y)) { //이동가능 하다면 swap
fish tmp = map[next_x][next_y];
map[next_x][next_y] = { num, next_dir };
map[x][y] = tmp;
fishInfo[num] = { next_x, next_y };
fishInfo[tmp.num] = { x,y };
break;
}
}
}
자세한 내용은 하단의 소스코드에 주석을 남겨두었음
소스 코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef struct fish {
int num, dir;
};
typedef struct info {
int x, y, dir, cost;
};
pair<int, int> direction[8] = { {-1, 0}, {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1} };
fish map[4][4];
info shark;
int result = 0;
bool inRange(int x, int y) {
return (0 <= x && x < 4 && 0 <= y && y < 4);
}
vector<vector<fish>> copy() {
vector<vector<fish>> repos(4, vector<fish>(4));
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
repos[i][j] = map[i][j];
return repos;
}
void restore(vector<vector<fish>> repos) {
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
map[i][j] = repos[i][j];
}
void move(vector<pair<int, int>> &fishInfo, info shark, int num) {
//한 마리의 물고기에 대한 처리
//실시간으로 fishInfo를 업데이트 해야 하므로 참조 연산자 사용
int x = fishInfo[num].first;
int y = fishInfo[num].second;
int dir = map[x][y].dir;
for (int i = 0; i < 8; i++) { //반 시계 방향으로 방향 전환
int next_dir = (dir + i) % 8;
int next_x = x + direction[next_dir].first;
int next_y = y + direction[next_dir].second;
if (inRange(next_x, next_y) && !(next_x == shark.x && next_y == shark.y)) { //이동가능 하다면 swap
fish tmp = map[next_x][next_y];
map[next_x][next_y] = { num, next_dir };
map[x][y] = tmp;
fishInfo[num] = { next_x, next_y };
fishInfo[tmp.num] = { x,y };
break; // 물고기 이동 후 종료
}
}
}
void moveAll(info &shark) { // 전체 물고기에 대해
vector<pair<int, int>> fishInfo(17, {-1,-1}); //n번 물고기와 좌표를 매핑
for (int i = 0; i < 4; i++)
for (int j = 0; j < 4; j++)
if (!(i == shark.x && j == shark.y))
if (map[i][j].num != 0)
fishInfo[map[i][j].num] = { i,j };
for (int i = 1; i < 17; i++)
if (fishInfo[i].first != -1)
move(fishInfo, shark, i); //1번 부터 1마리 씩 이동
}
bool goHome(info &shark) {
int x = shark.x;
int y = shark.y;
while (inRange(x, y)) { //범위 안에서 물고기가 있는지 확인
if (map[x][y].num != 0)
return false;
x += direction[shark.dir].first;
y += direction[shark.dir].second;
}
return true;
}
void solve(info shark) {
//repos를 전역변수로 사용한다면 다른 dfs에서 repos의 상태를 변화시킬 수 있으므로 불가능
vector<vector<fish>> repos = copy();
moveAll(shark); // 물고기 전부 이동
if (goHome(shark)) { //먹을 먹이가 없다면
result = max(shark.cost, result); //결과 갱신
restore(repos); //map복원
return;
}
else {
int x = shark.x + direction[shark.dir].first;
int y = shark.y + direction[shark.dir].second;
while (inRange(x, y)) {
if (map[x][y].num != 0) {
fish tmp = map[x][y];
map[x][y] = { 0, 0 }; //해당 좌표의 물고기를 먹음
solve({ x, y, tmp.dir, shark.cost + tmp.num }); //next
map[x][y] = tmp; //back
}
x += direction[shark.dir].first;
y += direction[shark.dir].second;
}
restore(repos); //map 복원
}
}
int main() {
ios_base::sync_with_stdio(false);
cout.tie(0);
cin.tie(0);
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
int num, dir;
cin >> num >> dir;
map[i][j] = { num, dir - 1 };
}
}
shark = { 0,0, map[0][0].dir, map[0][0].num };
map[0][0] = { 0,0 };
result = shark.cost;
solve(shark);
cout << result << "\n";
}
'알고리즘 > 백준' 카테고리의 다른 글
| [C++] 백준 20056 마법사 상어와 파이어볼 (0) | 2021.01.10 |
|---|---|
| [C++] 백준 20057 마법사 상어와 토네이도 (0) | 2021.01.06 |
| [C++] 백준 20061 모노미노도미노 (0) | 2021.01.05 |
| [C++] 백준 17472 다리만들기2 (0) | 2021.01.04 |
| [C++] 백준 17281 야구 (0) | 2021.01.04 |
