Life Engineering
[BOJ 19236] 청소년 상어 (C++) 본문
https://www.acmicpc.net/problem/19236https://www.acmicpc.net/problem/19236
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dx[8] = { -1,-1,0,1,1,1,0,-1 };
int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
struct fish {
int num;
int pos;
};
struct info {
int shark_x, shark_y;
vector<vector<fish> > graph;
vector<pair<int, int> > v;
int cnt;
};
void moveFish(vector<vector<fish> >& graph, vector<pair<int, int>>& v) {
int x, y, pos, cnt;
for (int i = 1; i <= 16; i++) {
if (v[i].first == -1) //탐색x
continue;
x = v[i].first;
y = v[i].second;
pos = graph[x][y].pos;
cnt = 8;
while (cnt--) {
int nx = x + dx[pos];
int ny = y + dy[pos];
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
if (graph[nx][ny].num == 0) { //빈칸
v[i].first = nx;
v[i].second = ny;
graph[nx][ny].num = i;
graph[nx][ny].pos = pos;
graph[x][y].num = 0;
break;
}
else if (graph[nx][ny].num >= 1 && graph[nx][ny].num <= 16) {
int temp_num = graph[nx][ny].num;
int temp_pos = graph[nx][ny].pos;
v[i].first = nx;
v[i].second = ny;
v[temp_num].first = x;
v[temp_num].second = y;
graph[nx][ny].num = i;
graph[nx][ny].pos = pos;
graph[x][y].num = temp_num;
graph[x][y].pos = temp_pos;
break;
}
}
pos = (pos + 1) % 8;
}
}
}
int main() {
vector<vector<fish> > graph(4);
vector<pair<int, int> > v(17);
int a, b;
int ans = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
cin >> a >> b;
graph[i].push_back({ a,b-1 });
v[a] = { i,j };
}
}
//shark 이동
int prev_pos = graph[0][0].pos;
int prev_num = graph[0][0].num;
v[prev_num] = { -1,-1 }; //(0,0) 자리에 위치한
graph[0][0] = { 17,prev_pos }; //17: 상어
queue<info> q;
q.push({ 0,0,graph,v,prev_num });
while (!q.empty()) {
int possible = 0;
info i = q.front();
q.pop();
//goal check
int next_x = i.shark_x + dx[i.graph[i.shark_x][i.shark_y].pos];
int next_y = i.shark_y + dy[i.graph[i.shark_x][i.shark_y].pos];
if (next_x < 0 || next_x >= 4 || next_y < 0 || next_y >= 4) {
ans = max(ans, i.cnt);
continue;
}
//물고기 이동
moveFish(i.graph, i.v);
//가능한 쪽으로 상어 이동하여 큐에 넣기
int shark_pos = i.graph[i.shark_x][i.shark_y].pos;
int new_shark_x = i.shark_x + dx[shark_pos];
int new_shark_y = i.shark_y + dy[shark_pos];
while (new_shark_x >= 0 && new_shark_x < 4 && new_shark_y >= 0 && new_shark_y < 4) {
if (i.graph[new_shark_x][new_shark_y].num != 0) {
vector<vector<fish> > new_graph = i.graph;
vector<pair<int, int> > nv = i.v;
new_graph[i.shark_x][i.shark_y].num = 0;
int prey = new_graph[new_shark_x][new_shark_y].num;
nv[prey] = { -1,-1 };
new_graph[new_shark_x][new_shark_y].num = 17;
q.push({ new_shark_x, new_shark_y, new_graph, nv, i.cnt + prey });
possible++;
}
new_shark_x += dx[shark_pos];
new_shark_y += dy[shark_pos];
}
if (possible == 0) { //방향으로 모두 빈칸일때, 집에 가므로 ans 계산
ans = max(ans, i.cnt);
}
}
cout << ans << "\n";
return 0;
}
시뮬레이션+백트래킹(DFS) 문제였다.
나는 큐를 이용해서 거의 BFS 방식으로 풀었는데, 깔끔하게 풀리지 않았다. 예외처리도 곳곳에 해줘야했다.
DFS를 사용해서 완전탐색, 백트래킹을 해주는게 출제자의 의도같다.
다른 분의 코드를 보니(https://yjyoon-dev.github.io/boj/2020/11/17/boj-19236/)
solve(y,x): (y,x) 자리 물고기를 먹고 난 이후 누적합 반환한다.
상어가 이동한 상태=>물고기 움직임=>다음 상어의 움직임 재귀로 호출해준다.
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 카펫 (C++) (0) | 2021.10.21 |
---|---|
[프로그래머스] 위장 (Python3) (0) | 2021.10.21 |
[BOJ 21608] 상어 초등학교 (C++) (0) | 2021.10.18 |
[BOJ 17779] 게리맨더링 2 (C++) (0) | 2021.10.18 |
[프로그래머스] 여행경로 (Python3) (0) | 2021.10.17 |