문제
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기, 블리자드 마법을 할 수 있다. 오늘은 기존에 배운 물복사버그 마법의 상위 마법인 복제를 배웠고, 4 × 4 크기의 격자에서 연습하려고 한다. (r, c)는 격자의 r행 c열을 의미한다. 1) 격자의 가장 왼쪽 윗 칸은 (1, 1)이고, 가장 오른쪽 아랫 칸은 (4, 4)이다.
격자에는 물고기 M마리가 있다. 2) 각 물고기는 격자의 칸 하나에 들어가 있으며, 이동 방향을 가지고 있다. 이동 방향은 8가지 방향(상하좌우, 대각선) 중 하나이다. 마법사 상어도 연습을 위해 격자에 들어가있다. 상어도 격자의 한 칸에 들어가있다. 3) 둘 이상의 물고기가 같은 칸에 있을 수도 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수도 있다.
상어의 마법 연습 한 번은 다음과 같은 작업이 순차적으로 이루어진다.
- 상어가 모든 물고기에게 복제 마법을 시전한다. 복제 마법은 시간이 조금 걸리기 때문에, 아래 5번에서 물고기가 복제되어 칸에 나타난다.
- 모든 물고기가 한 칸 이동한다. 상어가 있는 칸, 물고기의 냄새가 있는 칸, 격자의 범위를 벗어나는 칸으로는 이동할 수 없다. 각 물고기는 자신이 가지고 있는 이동 방향이 이동할 수 있는 칸을 향할 때까지 방향을 45도 반시계 회전시킨다. 만약, 이동할 수 있는 칸이 없으면 이동을 하지 않는다. 그 외의 경우에는 그 칸으로 이동을 한다. 물고기의 냄새는 아래 3에서 설명한다.
- 상어가 연속해서 3칸 이동한다. 상어는 현재 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 연속해서 이동하는 칸 중에 격자의 범위를 벗어나는 칸이 있으면, 그 방법은 불가능한 이동 방법이다. 연속해서 이동하는 중에 상어가 물고기가 있는 같은 칸으로 이동하게 된다면, 그 칸에 있는 모든 물고기는 격자에서 제외되며, 제외되는 모든 물고기는 물고기 냄새를 남긴다. 가능한 이동 방법 중에서 제외되는 물고기의 수가 가장 많은 방법으로 이동하며, 그러한 방법이 여러가지인 경우 사전 순으로 가장 앞서는 방법을 이용한다. 사전 순에 대한 문제의 하단 노트에 있다.
- 두 번 전 연습에서 생긴 물고기의 냄새가 격자에서 사라진다.
- 1에서 사용한 복제 마법이 완료된다. 모든 복제된 물고기는 1에서의 위치와 방향을 그대로 갖게 된다.
격자에 있는 물고기의 위치, 방향 정보와 상어의 위치, 그리고 연습 횟수 S가 주어진다. S번 연습을 모두 마쳤을때, 격자에 있는 물고기의 수를 구해보자.
입력
첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향은 8 이하의 자연수로 표현하고, 1부터 순서대로 ←, ↖, ↑, ↗, →, ↘, ↓, ↙ 이다. 마지막 줄에는 sx, sy가 주어지며, 상어가 (sx, sy)에 있음을 의미한다.
격자 위에 있는 물고기의 수가 항상 1,000,000 이하인 입력만 주어진다.
출력
S번의 연습을 마친 후 격자에 있는 물고기의 수를 출력한다.
제한
- 1 ≤ M ≤ 10
- 1 ≤ S ≤ 100
- 1 ≤ fx, fy, sx, sy ≤ 4
- 1 ≤ d ≤ 8
- 두 물고기 또는 물고기와 상어가 같은 칸에 있을 수도 있다.
노트
상어의 이동 방법 중 사전 순으로 가장 앞서는 방법을 찾으려면 먼저, 방향을 정수로 변환해야 한다. 상은 1, 좌는 2, 하는 3, 우는 4로 변환한다. 변환을 모두 마쳤으면, 수를 이어 붙여 정수로 하나 만든다. 두 방법 A와 B가 있고, 각각을 정수로 변환한 값을 a와 b라고 하자. a < b를 만족하면 A가 B보다 사전 순으로 앞선 것이다.
예를 들어, [상, 하, 좌]를 정수로 변환하면 132가 되고, [하, 우, 하]를 변환하면 343이 된다. 132 < 343이기 때문에, [상, 하, 좌]가 [하, 우, 하]보다 사전 순으로 앞선다.
총 43 = 64가지 방법을 사전 순으로 나열해보면 [상, 상, 상], [상, 상, 좌], [상, 상, 하], [상, 상, 우], [상, 좌, 상], [상, 좌, 좌], [상, 좌, 하], [상, 좌, 우], [상, 하, 상], ..., [우, 하, 하], [우, 하, 우], [우, 우, 상], [우, 우, 좌], [우, 우, 하], [우, 우, 우] 이다.
구현해야할 조건
격자의 크기는 4칸으로 고정되어있기 때문에, 뭔짓을 해도 시간초과는 나지 않을 것 같다. 둘 이상의 물고기가 같은 칸에 있을 수 있으며, 마법사 상어와 물고기가 같은 칸에 있을 수 있다. 라는 조건을 봤을때 vector로 map을 짜야한다.
복제는 초반 vector에서 물고기들을 뽑아서 나중에 복제를 시켜주는 것과, 구현을 해주고, 상어의 이동에서 백트랙킹을 사용해서 문제를 해결했지만 3중 포문으로 해결을 해도 괜찮을것 같다 4*4니까, 냄새 부분도 구현을 잘 해주고 상세 내용을 구현을 잘 해야 문제 해결이 더 쉽다.
code
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstring>
#define MAX 5
using namespace std;
typedef struct{
int y;
int x;
int dir;
}fishes;
const int dx[9] = {0,-1,-1,0,1,1,1,0,-1};
const int dy[9] = {0,0,-1,-1,-1,0,1,1,1}; // 0,9시부터 시계방향으로 돌아가는 것
const int sx[5] = {0,0,-1,0,1};
const int sy[5] = {0,-1,0,1,0}; // shark_move
int m,s;
vector<int> map[MAX][MAX]; // fish가 저장되어있는 장소
queue<fishes> copy_fish; // 복제할 fish들
vector<pair<int,int> > shark; // 상어의 위치 뽑아주기
vector<int> direction;
vector<string> shark_dir;
vector<pair<string,int> > sorted_shark;
int shark_location[MAX][MAX];
int smell[MAX][MAX];
bool comp(pair<string,int> &a, pair<string,int> &b)
{
if(a.second == b.second)
return a.first < b.first; // 가장 많이 먹는 순이 같으면 우선순위 비교
return a.second > b.second; // 가장 많이 먹는 순
}
void move_fish()
{
queue<fishes> fish;
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
if(map[i][j].size() >= 1)
{
for(int s = 0; s < map[i][j].size(); s++)
{
fish.push({i,j,map[i][j][s]});
copy_fish.push({i,j,map[i][j][s]}); // 복제마법
}
}
map[i][j].clear();
}
}
while(!fish.empty())
{
int y = fish.front().y;
int x = fish.front().x;
int dir = fish.front().dir;
fish.pop();
int current = dir;
while(1)
{
int ny = y + dy[dir];
int nx = x + dx[dir];
if(smell[ny][nx] || shark_location[ny][nx] || !(1 <= ny && ny <= 4 && 1 <= nx && nx <= 4))
{
dir -= 1;
if(dir == 0)
dir = 8; // 냄새가 있는곳, 또는 상어의 위치, 또는 범위를 벗어나는 것
}
else
{
map[ny][nx].push_back(dir); // 이동한 곳에 넣고 break
break;
}
if(current == dir)
{
map[y][x].push_back(current); // 현재 위치랑 같다? 즉 돌아왔다면 break
break;
}
}
}
}
void DFS(int cnt)
{
if(cnt == 3) // 3칸을 이동하는 것이기 때문에 쉽게 생각하면 3번 전부 완탐
{
int temp_fish[MAX][MAX];
string str = ""; // 우선순위 비교를 위해 string으로 해결
for(int i = 0; i < direction.size(); i++)
str += to_string(direction[i]);
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
temp_fish[i][j] = map[i][j].size();
}
}
bool chk = true;
int res = 0;
int y = shark[0].first;
int x = shark[0].second;
for(int i = 0; i < direction.size(); i++)
{
int ny = y + sy[direction[i]];
int nx = x + sx[direction[i]];
if(1 <= ny && ny <= 4 && 1 <= nx && nx <= 4)
{
res += temp_fish[ny][nx];
y += sy[direction[i]];
x += sx[direction[i]];
temp_fish[ny][nx] = 0;
}
else
{
chk = false;
break;
}
}
if(chk)
sorted_shark.push_back({str,res});
return;
}
for(int i = 1; i <= 4; i++)
{
direction.push_back(i);
DFS(cnt+1);
direction.pop_back();
}
}
void move_shark()
{
sort(sorted_shark.begin(), sorted_shark.end(),comp); // 전체 다 구한 것을 sort해주고
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j<= 4; j++)
{
if(smell[i][j])
smell[i][j]++; // 냄새 있는 곳 두번 전에 사라지니까 증가해주고
}
}
int dir = stoi(sorted_shark[0].first);
vector<int> d;
int first = dir/100;
d.push_back(first);
dir %= 100;
int second = dir/10;
d.push_back(second);
dir %= 10;
d.push_back(dir); // string 파싱해준후에
shark_location[shark[0].first][shark[0].second] = 0; 상어의 위치를 넣어주고 이동 시작
int y = shark[0].first;
int x = shark[0].second;
for(int i = 0; i < d.size(); i++)
{
int ny = y + sy[d[i]];
int nx = x + sx[d[i]];
if(map[ny][nx].size() >= 1) // 상어 이동하면서 물고기 잡아먹기 가능? 쌉가능
smell[ny][nx] = 1;
map[ny][nx].clear();
y += sy[d[i]];
x += sx[d[i]];
}
shark_location[y][x] = 1; // 상어의 위치 remake
sorted_shark.clear(); // 상어 이동순위 지워주기
}
void fade_smell()
{
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
if(smell[i][j] == 3) // 두번 전은 사라지니까 3이되면 2번 전
{
smell[i][j] = 0;
}
}
}
}
int main()
{
cin >> m >> s;
for(int i = 0; i < m; i++)
{
int y,x,d;
cin >> y >> x >> d;
map[y][x].push_back(d);
}
int y,x;
cin >> y >> x;
shark_location[y][x] = 1;
while(s--)
{
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
if(shark_location[i][j])
shark.push_back({i,j});
}
} // shark의 위치 넣어주고
move_fish();
DFS(0);
move_shark();
fade_smell(); // smell[y][x]가 3이면 삭제
while(!copy_fish.empty()) // 복사해주고
{
int y = copy_fish.front().y;
int x = copy_fish.front().x;
int d = copy_fish.front().dir;
copy_fish.pop();
map[y][x].push_back(d);
}
shark.pop_back();// shark의 위치 빼주고
}
int ans = 0;
for(int i = 1; i <= 4; i++)
{
for(int j = 1; j <= 4; j++)
{
if(map[i][j].size() >= 1)
{
ans += map[i][j].size(); // 전체 사이즈 구하기!
}
}
}
cout << ans;
return 0;
}
code [다시 풀었을때 주의해야할 점을 발견해 다시 올립니다]
#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
typedef struct{
int y;
int x;
int dir;
}Fish;
const int dx[9] = {0,-1,-1,0,1,1,1,0,-1};
const int dy[9] = {0,0,-1,-1,-1,0,1,1,1}; // 물고기의 이동
const int shark_dx[5] = {0,0,-1,0,1};
const int shark_dy[5] = {0,-1,0,1,0}; // 상어의 이동
int res = 0;
int m,s,shark_y,shark_x;
int smell[5][5];
vector<int> direction;
vector<int> board[5][5];
vector<pair<int,string> > st;
vector<pair<int,int> > shark;
vector<pair<pair<int,int>,int> > v;
bool comp(pair<int,string> a, pair<int,string> b){
if(a.first == b.first)
return a.second < b.second;
return a.first > b.first;
}
queue<Fish> copy(){
queue<Fish> q;
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
if(board[i][j].size() > 0){
for(int k = 0; k < board[i][j].size(); k++){
q.push({i,j,board[i][j][k]});
}
}
}
}
return q;
}
void move(){
queue<Fish> q;
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
if(board[i][j].size() > 0){
for(int k = 0; k < board[i][j].size(); k++){
q.push({i,j,board[i][j][k]});
}
board[i][j].clear(); // 삭제작업
}
}
}
while(!q.empty()){
int y = q.front().y;
int x = q.front().x;
int dir = q.front().dir;
bool chk = false;
int current = dir;
q.pop();
while(1){
int ny = y + dy[dir];
int nx = x + dx[dir];
/*
냄새가 있는곳, 또는, 상어가 있는 곳 또는, 범위를 벗어나면 방향을 돌려준다!
*/
if(smell[ny][nx] || (ny == shark[0].first && nx == shark[0].second) || !(1 <= ny && ny <= 4 && 1 <= nx && nx <= 4)){
dir -= 1;
if(dir == 0)
dir = 8;
}
else{ // 그렇지 않으면 그냥 추가
board[ny][nx].push_back(dir);
break;
}
//방향을 돌려도 그대로 라면 그대로!
if(current == dir){
board[y][x].push_back(current);
break;
}
}
}
}
void shark_move(int cnt){
if(cnt == 3){
int temp_fish[5][5];
string str = "";
for(int i = 0; i < direction.size(); i++)
str += to_string(direction[i]);
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
temp_fish[i][j] = board[i][j].size();
}
}
bool chk = true;
int res = 0;
int y = shark[0].first;
int x = shark[0].second;
for(int i = 0; i < direction.size(); i++){
int ny = y + shark_dy[direction[i]];
int nx = x + shark_dx[direction[i]];
/*
이동시에 모든 조합을 사용해야하는데, 범위 안에 있는 것만 체크를 한다.
왜냐하면, 정렬을 하는데 오히려 왔다 갔다 하는게 더 점수를 얻을 경우가 있다.
그래서 visited를 사용해서 문제를 해결하면, 제외되기 때문에 이점을 생각해야한다.
*/
if(1 <= ny && ny <= 4 && 1 <= nx && nx <= 4){
res += temp_fish[ny][nx];
y += shark_dy[direction[i]];
x += shark_dx[direction[i]];
temp_fish[ny][nx] = 0;
}
else{
chk = false;
break;
}
}
if(chk)
st.push_back({res,str});
return;
}
for(int i = 1; i <= 4; i++){
direction.push_back(i);
shark_move(cnt+1);
direction.pop_back();
}
}
void shark_move2(int y, int x, string str){
int ny,nx;
vector<int> dir;
int d = stoi(str);
int first = d/100;
dir.push_back(first);
d %= 100;
int second = d/10;
dir.push_back(second);
d %= 10;
dir.push_back(d);
for(int i = 0; i < dir.size(); i++){
ny = y + shark_dy[dir[i]];
nx = x + shark_dx[dir[i]];
if(board[ny][nx].size()){
board[ny][nx].clear();
smell[ny][nx] = 3;
}
x = nx;
y = ny;
}
shark.pop_back();
shark.push_back({ny,nx});
}
void fade(){
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
if(smell[i][j] > 0)
smell[i][j]--;
}
}
}
int main(){
cin >> m >> s;
for(int i = 0; i < m; i++){
int y,x,dir;
cin >> y >> x >> dir;
board[y][x].push_back(dir);
}
cin >> shark_y >> shark_x;
shark.push_back({shark_y,shark_x});
while(s--){
queue<Fish> q = copy();
move();
st.clear();
shark_move(0);
sort(st.begin(), st.end(), comp);
shark_move2(shark[0].first, shark[0].second, st[0].second);
fade();
while(!q.empty()){
int y = q.front().y;
int x = q.front().x;
int d = q.front().dir;
q.pop();
board[y][x].push_back(d);
}
}
int res = 0;
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
res += board[i][j].size();
}
}
cout << res;
return 0;
}'PS > Samsung' 카테고리의 다른 글
| [백준/c++] 21609 상어 중학교 (0) | 2022.04.08 |
|---|---|
| [백준/c++] 21608 상어 초등학교 (0) | 2022.04.07 |
| [백준/c++] 20058 마법사 상어와 파이어스톰 (0) | 2022.04.06 |
| [백준/c++] 20057 마법사 상어와 토네이도 (0) | 2022.04.06 |
| [백준/c++] 23288 주사위 굴리기2 (0) | 2022.02.24 |
