1- // Authored by : BaaaaaaaaaaarkingDog
1+ // Authored by : scsc3204
22// Co-authored by : -
3- // http://boj.kr/****************
3+ // http://boj.kr/5391b877c86d44c98e183321064cbdea
44#include < bits/stdc++.h>
5+ #define X first
6+ #define Y second
57using namespace std ;
68
7- int main (void ){
9+ const int shk = 17 ;
10+
11+ vector<vector<pair<int , int >>> board (4 );
12+ vector<pair<int , int >> coord;
13+
14+ int dx[] = {-1 , -1 , 0 , 1 , 1 , 1 , 0 , -1 };
15+ int dy[] = {0 , -1 , -1 , -1 , 0 , 1 , 1 , 1 };
16+
17+ bool oob (int x, int y) {
18+ return x >= 4 || x < 0 || y >= 4 || y < 0 ;
19+ }
20+
21+ int solve (vector<vector<pair<
int ,
int >>> b, vector<pair<
int ,
int >> co) {
22+ for (int no = 1 ; no <= 16 ; no++) {
23+ auto [cx, cy] = co[no];
24+ if (cx == -1 || cy == -1 ) continue ;
25+ int dir = b[cx][cy].Y ;
26+ int nx = cx + dx[dir];
27+ int ny = cy + dy[dir];
28+ while (oob (nx, ny) || b[nx][ny].X == shk) {
29+ dir = (dir + 1 ) % 8 ;
30+ nx = cx + dx[dir];
31+ ny = cy + dy[dir];
32+ }
33+ b[cx][cy].Y = dir;
34+
35+ co[no] = {nx, ny};
36+ co[b[nx][ny].X ] = {cx, cy};
37+ b[cx][cy] = b[nx][ny];
38+ b[nx][ny] = {no, dir};
39+ }
40+
41+ int ans = 0 ;
42+ auto [cx, cy] = co[shk];
43+ int dir = b[cx][cy].Y ;
44+ for (int p = 1 ; p <= 3 ; p++) {
45+ int nx = cx + p * dx[dir];
46+ int ny = cy + p * dy[dir];
47+ if (oob (nx, ny) || !b[nx][ny].X ) continue ;
48+
49+ vector<vector<pair<int , int >>> tmpb = b;
50+ vector<pair<int , int >> tmpco = co;
51+ int no = tmpb[nx][ny].X ;
52+ tmpb[nx][ny].X = shk;
53+ tmpco[shk] = {nx, ny};
54+ tmpco[no] = {-1 , -1 };
55+ tmpb[cx][cy] = {0 , 0 };
56+ ans = max (ans, no + solve (tmpb, tmpco));
57+ }
58+ return ans;
59+ }
60+
61+ void setup () {
62+ coord.resize (19 );
63+ for (int i = 0 ; i < 4 ; i++) {
64+ board[i].resize (4 );
65+ for (int j = 0 ; j < 4 ; j++) {
66+ int no, dir; cin >> no >> dir;
67+ board[i][j] = {no, dir - 1 };
68+ coord[no] = {i, j};
69+ }
70+ }
71+ }
72+
73+ int main () {
874 ios::sync_with_stdio (0 );
975 cin.tie (0 );
10-
11- }
76+
77+ setup ();
78+ int no = board[0 ][0 ].X ;
79+ board[0 ][0 ].X = shk;
80+ coord[no] = {-1 , -1 };
81+ coord[shk] = {0 , 0 };
82+ cout << no + solve (board, coord) << ' \n '
83+ }
84+ /*
85+ 0은 물고기가 없는 칸을 의미하며, 1부터 16까지의 수를 물고기의 번호로 둔다.
86+ 17은 상어의 번호로 지정하여 구현한다.
87+
88+ setup 함수: 58-68번째 줄
89+ - 초기 정보를 board와 coord 벡터에 저장하며, board[x][y]에는 번호와 방향이 pair로 저장된다(64번째 줄).
90+ - coord[no]는 물고기 또는 상어의 위치를 1부터 17까지 번호를 통해 인덱싱한다(65번째 줄).
91+
92+ board와 coord 벡터를 solve 함수에 전달하며 백트래킹한다.
93+
94+ solve 함수: 18-56번째 줄
95+ 1. 물고기 이동 구현
96+ - 넘겨받은 상태(벡터 b와 co에 복사)에 대해 상어가 먹을 수 있는 최대 물고기 번호를 반환한다.
97+ - 1번부터 16번 물고기를 이동시키는 for문: 19-36번째 줄.
98+ - 먹힌 고기는 co 벡터의 값을 {-1, -1}로 설정할 것이므로, 이에 해당하면 다음 번호를 확인한다(21번째 줄).
99+ - 다음 위치가 판을 벗어나거나 상어가 위치한 경우에는 방향을 바꾸고 nx, ny를 갱신한다(25-29번째 줄).
100+ 이후 얻은 방향을 현위치의 dir 값으로 갱신한다(30번째 줄).
101+ - cx, cy에 위치한 정보와 nx, ny에 위치한 정보를 교환한다(32-35번째 줄).
102+
103+ 2. 상어 이동 및 백트래킹 구현
104+ - 상어의 위치와 방향을 가져온다. 판의 제약사항으로 인해 상어가 최대 3칸까지 이동이 가능하므로,
105+ 좌표의 증가량 p를 최대 3까지만 설정한다(41번째 줄).
106+ - 문제 조건에 따라 비어있는 칸에는 상어가 가지 못하므로, 판을 벗어나는 경우와 함께 경우에서 배제한다(44번째 줄).
107+ - 이후 tmpb와 tmpco에 b와 co 벡터를 복사하고, 상어를 배치한다(46-52번째 줄).
108+ - 상어는 해당 물고기의 방향을 유지하며 위치만 가져간다(49-50번째 줄).
109+ - 상어에게 먹힌 물고기는 위치를 -1, -1로 바꾸고, no은 0으로 바꿔 비어있음을 나타낸다(51-52번째 줄).
110+ - 이후 갱신된 tmpb와 tmpco를 인자로 념겨준 solve 함수와 먹은 물고기 번호의 합을 ans 값과 비교하며 갱신한다(53번째 줄).
111+ - solve함수는 최종적으로 갱신된 가장 큰 ans 값을 반환한다(55번쨰 줄).
112+ */
0 commit comments