1- // Authored by : BaaaaaaaaaaarkingDog
1+ // Authored by : scsc3204
22// Co-authored by : -
3- // http://boj.kr/****************
3+ // http://boj.kr/c25a30dd61f24dde92937343edb55a44
44#include < bits/stdc++.h>
55using namespace std ;
66
7- int main (void ){
7+ const int MX = 20 ;
8+
9+ int dx[] = {1 , 0 , -1 , 0 };
10+ int dy[] = {0 , 1 , 0 , -1 };
11+
12+ int n, u, v, mx, ans;
13+
14+ int score[MX + 2 ][MX + 2 ];
15+ int vctcnt[MX + 2 ][MX + 2 ];
16+ int b[MX + 2 ][MX + 2 ];
17+ int pref[MX*MX + 2 ][4 ];
18+
19+ pair<int , int > ps[MX*MX + 2 ];
20+ vector<tuple<int , int , int >> cand;
21+
22+ bool OOB (int x, int y) {
23+ return (x >= n || x < 0 || y >= n || y < 0 );
24+ }
25+
26+ void setup () {
27+ cin >> n;
28+ for (int i = 1 ; i <= n*n; i++)
29+ ps[i] = {-1 , -1 };
30+
31+ for (int i = 0 ; i < n; i++)
32+ for (int j = 0 ; j < n; j++) {
33+ vctcnt[i][j] = 4 ;
34+ if (i == 0 || i == n - 1 ) vctcnt[i][j]--;
35+ if (j == 0 || j == n - 1 ) vctcnt[i][j]--;
36+ }
37+ }
38+
39+ void init () {
40+ for (int i = 0 ; i < n; i++)
41+ fill (score[i], score[i] + n, 0 );
42+ mx = 0 ;
43+ cand.clear ();
44+ }
45+
46+ void setprefer () {
47+ cin >> u;
48+ for (int j = 0 ; j < 4 ; j++) {
49+ cin >> v;
50+ pref[u][j] = v;
51+ auto [cx, cy] = ps[v];
52+ if (cx == -1 && cy == -1 ) continue ;
53+ for (int dir = 0 ; dir < 4 ; dir++) {
54+ int nx = cx + dx[dir];
55+ int ny = cy + dy[dir];
56+ if (OOB (nx, ny) || b[nx][ny]) continue ;
57+ score[nx][ny]++;
58+ mx = max (mx, score[nx][ny]);
59+ }
60+ }
61+ }
62+
63+ void setseat () {
64+ for (int i = 0 ; i < n; i++)
65+ for (int j = 0 ; j < n; j++)
66+ if (mx == score[i][j] && !b[i][j])
67+ cand.push_back ({-vctcnt[i][j], i, j});
68+
69+ sort (cand.begin (), cand.end ());
70+ auto [vcnt, x, y] = cand[0 ];
71+
72+ ps[u] = pair<int , int >(x, y);
73+ b[x][y] = u;
74+
75+ for (int dir = 0 ; dir < 4 ; dir++) {
76+ int nx = x + dx[dir];
77+ int ny = y + dy[dir];
78+ if (OOB (nx, ny)) continue ;
79+ vctcnt[nx][ny]--;
80+ }
81+ }
82+
83+ void calc () {
84+ for (int i = 1 ; i <= n*n; i++) {
85+ int cnt = 0 ;
86+ auto [cx, cy] = ps[i];
87+ for (int j = 0 ; j < 4 ; j++) {
88+ auto [nx, ny] = ps[pref[i][j]];
89+ if (abs (nx - cx) + abs (ny - cy) != 1 ) continue ;
90+ cnt++;
91+ }
92+ if (!cnt) continue ;
93+ int a = 1 ;
94+ while (--cnt) a *= 10 ;
95+ ans += a;
96+ }
97+ }
98+
99+ int main () {
8100 ios::sync_with_stdio (0 );
9101 cin.tie (0 );
10-
11- }
102+
103+ setup ();
104+ for (int i = 1 ; i <= n*n; i++) {
105+ init ();
106+ setprefer ();
107+ setseat ();
108+ }
109+ calc ();
110+ cout << ans;
111+ }
112+ /*
113+ setup 함수(26-37번째 줄)
114 + - 인원들의 위치를 ps 배열에 미정 상태(-1, -1)로 설정
115+ - 인접한 칸 중에서 비어있는 칸을 세서 vctcnt에 기록
116+
117+ init 함수(39-44번째 줄)
118+ - 자리별 점수를 기록하는 score 배열 초기화
119+ - 점수 중 최댓값을 기록하는 mx에 0 할당
120+ - 비어있는 칸의 수와 행 번호, 열 번호를 받아 자리 후보를 기록하는 cand 벡터 초기화
121+
122+ setprefer 함수(46-61번째 줄)
123+ - 이번 좌석 배정의 대상이 되는 학생 번호, u를 입력 받음(47번째 줄)
124+ - 좋아하는 친구 목록을 기록하면서 좋아하는 친구가 있는 자리를 확인
125+ - 좋아하는 친구가 아직 자리를 정하지 못한 경우(52번째 줄) 다음 좋아하는 친구를 확인
126+ - 좋아하는 친구가 자리에 앉아 있는 경우, 그 친구가 인접한 빈자리들에 점수를 추가
127+ - 점수 최댓값을 mx에 갱신
128+
129+ setseat 함수(63-81번째 줄)
130+ - 좋아하는 학생이 가장 많은 칸들을 cand에 기록
131+ - cand에는 비어있는 칸 수를 센 vcnt와 행 번호 x, 열 번호 y를 (-vcnt, x, y)로 삽입한다.
132+ - cand를 정렬하면 vcnt가 내림차순으로 정렬되고,
133+ 행 번호의 오름차순, 열 번호의 오름차순으로 각각 정렬 우선 순위가 낮아진다.
134+ 따라서 이렇게 정렬된 가장 첫번째 원소인 cand[0]를 꺼내 b[x][y]에 좌석 배정의 대상이 되는 학생 번호를 기록
135+
136+ calc 함수
137+ - 모든 학생의 자리 배정이 끝난 후 학생들의 인접한 위치에 있는 좋아하는 친구 수를 세고,
138+ 학생 수에 따라 점수를 계산하여 총 만족도를 기록하는 ans 변수에 더함
139+
140+ 이후 ans 값을 답으로 출력한다.
141+ */
0 commit comments