#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int ans;
pair<int,int> origin[4][4];
int dx[8] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
pair<pair<int,int>,int> shark_o;
deque<pair<int,int>> fish_o(16);
int rotate(int d){
d++;
if(d > 7) d -= 8;
return d;
}
void DFS(int tot, pair<int,int> board[4][4], pair<pair<int,int>,int> shark, deque<pair<int,int>> fish){
for(int i=0;i<fish.size();i++)
{
auto cur = fish[i];
if(cur.first == -1) continue;
int dir = board[cur.first][cur.second].second;
int ny = cur.first + dy[dir];
int nx = cur.second + dx[dir];
if((nx<0 or ny<0 or nx>=4 or ny>=4) or (shark.first.first == ny and shark.first.second == nx)){
dir = rotate(dir);
board[cur.first][cur.second].second = dir;
i--;
continue;
}
auto tmp = board[ny][nx];
if(tmp.first != -1){
auto save = fish[tmp.first-1];
fish[tmp.first-1] = fish[i];
fish[i] = save;
}else fish[i] = {ny,nx};
board[ny][nx] = board[cur.first][cur.second];
board[cur.first][cur.second] = tmp;
}
int ny = shark.first.first;
int nx = shark.first.second;
while(true)
{
pair<int,int> t_board[4][4];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
t_board[i][j] = board[i][j];
pair<pair<int,int>,int> t_shark = shark;
deque<pair<int,int>> t_fish(fish.begin(), fish.end());
int dir = t_shark.second;
ny += dy[dir];
nx += dx[dir];
if(nx<0 or ny<0 or nx>=4 or ny>=4) goto stop;
if(t_board[ny][nx].first == -1) continue;
int num = t_board[ny][nx].first;
t_fish[num-1] = {-1,-1};
t_shark.first = {ny,nx};
t_shark.second = t_board[ny][nx].second;
t_board[ny][nx] = {-1, -1};
ans = max(ans, tot + num);
DFS(tot + num, t_board, t_shark, t_fish);
}
stop:;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
{
int a,b;
cin >> a >> b;
origin[i][j] = {a,b-1};
fish_o[a-1] = {i,j};
}
auto tmp = origin[0][0];
int num = tmp.first;
origin[0][0] = {-1,-1};
fish_o[num-1] = {-1,-1};
shark_o = {{0,0},tmp.second};
pair<int,int> t_board[4][4];
for(int i=0;i<4;i++)
for(int j=0;j<4;j++)
t_board[i][j] = origin[i][j];
pair<pair<int,int>,int> t_shark = shark_o;
deque<pair<int,int>> t_fish(fish_o.begin(), fish_o.end());
DFS(num, t_board, t_shark, t_fish);
cout << ans;
return 0;
}
- 문제 풀이 접근
상어
가 어떤 물고기
를 먹는지
에 따라 결과
가 계속 달라짐
--> DFS
를 이용한 완전탐색
필요
- 고려해야할 것
순서가 진행
될 때 마다 board
/ shark
/ fish
변수가 달라진다
--> 매번 매개변수로 새로운 배열을 넘기거나
다시 배열을 복구
해주는 방법이 있다
(여기서 나는 매번 매개변수로 새로운 배열을 넘기는 방법
을 선택함)
- 오래걸린 이유
물고기가 없는 경우
에 board
만 갱신
하고, fish[]를 갱신하지 않음
--> 필요한 데이터
를 분산시켜 저장
해서 실수를 유발
함 --> 구조체
사용
dx[] / dy[]
방향 지정시 오타
가 있었다
--> 꼼꼼하게 체크
하자
rotate()
를 통해 반시계 45도 회전
을 했는데 시계방향
으로 했다
--> 역시 꼼꼼하게 체크
하자
- 느낀 것
DFS를 이용한 완전탐색
을 할 때 board
나 map
을 가지며 변경이 될 때
2가지 방법을 고민
하자
1) 매번 새로운 변수를 만들어서 매개변수로 넘기는 방법
: 매개변수로 값이 복사
되며 발생하는 시간복잡도
를 고려
해야 한다
--> 크기가 작을 때 가능
2) 백트래킹 (DFS 수행 후 변수 복구)
: copy하는 함수
를 별도로 만들거나 직접 반복문
을 돌려서 복구
(시간복잡도 측면
에서 백트래킹 방법이 더 안전
해 보임)
구조체
를 사용해보자
: 오래걸린 이유중 하나
가 무조건 pair<>을 쓰려는 경향
때문에 필요한 데이터가 분산되어 관리
하고 유지하기 까다로워
실수를 발생
시켰기 때문
--> 다음부터는 구조체
를 써서 필요한 데이터
를 응집시켜서 활용
하자