[코드트리] 꼬리잡기놀이 (삼성 SW 역량테스트 2022 상반기 오후 1번)

알고리즘/[ADV] 삼성 SW 역량 테스트 A형

[코드트리] 꼬리잡기놀이 (삼성 SW 역량테스트 2022 상반기 오후 1번)

피로물든딸기 2024. 6. 22. 00:33

삼성 A형 전체 링크

https://www.codetree.ai/training-field/frequent-problems/problems/tail-catch-play

MAP 정보는 다음과 같이 관리한다.

value는 입력으로 주어지는 0 ~ 4의 값이고, order는 입력의 1 ~ 3으로 주어지는 사람들의 순서가 된다.

loop는 꼬리잡기 루프를 식별하는 번호다.

이렇게 값을 정하면 MAP[r][c]에 사람이 있는 경우 점수를 바로 계산하고, 몇 번째 loop인지 알 수 있다.

그리고 BFS를 위해 visit을 선언한다.

typedef struct st1
{
	int value;
	int order;
	int loop;
}MAP_INFO;

MAP_INFO MAP[MAX][MAX];
int visit[MAX][MAX];

꼬리잡기를 하는 사람들의 좌표는 아래와 같이 관리한다.

rcData[loop]에 1 → 2 → ... → 3 → 4 순서대로 저장하게 된다.

rcIndex는 rcData의 개수(1 ~ 4)이며, rcPeople은 4를 제외한 1 ~ 3의 개수다.

direction은 모두 0으로 시작하고, loop에 있는 사람이 공을 맞은 경우 1로 변경된다.

typedef struct st2
{
	int r;
	int c;
	int order;
	int number;		
}RC;

RC rcData[5 + 2][MAX * MAX]; // 1, 2, 2, 3, 4, 4, 4, 4, 4, ... 의 좌표가 생성.
int rcIndex[5 + 2]; // 1 ~ 4의 수
int rcPeople[5 + 2]; // 1 ~ 3의 수
int direction[5 + 2];

그리고 좌표 탐색을 위한 dr, dc 배열을 정의한다.

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

input은 다음과 같다.

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c].value);
			MAP[r][c].loop = MAP[r][c].order = -1;
		}
	}

	for (int i = 0; i < M; i++)
		rcIndex[i] = rcPeople[i] = direction[i] = 0;
}

루프 찾기

input을 입력받고, 초기화를 완료하면 BFS를 이용해 loop를 찾는다.

MAP에서 머리사람에 해당하는 1을 찾은 후, 좌표 (r, c)와 loop 순서, visit 배열로 BFS를 실행한다.

BFS가 완료되면 loop를 1 증가해서 loop를 구분하였다.

(loop를 구분해야 direction을 체크하기 편하다.)

int main(void)
{	
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				visit[r][c] = 0;
		
		int loop = 0;
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c].value == 1 && visit[r][c] == 0)
				{
					BFS(r, c, loop, visit);				

					// printVisit(visit);
					// printRC(loop);

					loop++;
				}
			}
		}

		...
	}

	return 0;
}

BFS가 실행되었다는 것은, 머리사람(= 1)을 찾았다는 의미다.

따라서 방문 체크를 하고, MAP에는 loop와 order를 저장한다.

그리고 loop에 해당하는 rcData에 좌표와 입력된 사람의 순서, 사람의 번호(1 ~ 3)을 저장한다.

	RC queue[MAX * MAX] = { 0 };
	int wp, rp, order;

	wp = rp = 0;
	order = 1;
	
	visit[r][c] = 1;
	MAP[r][c].loop = loop;
	MAP[r][c].order = order;

	rcData[loop][rcIndex[loop]].r = r;
	rcData[loop][rcIndex[loop]].c = c;
	rcData[loop][rcIndex[loop]].order = order++;
	rcData[loop][rcIndex[loop]++].number = 1;

BFS를 실행하기 전에, 2를 먼저 찾는다.

2를 찾게 되면 1은 visit 처리가 되어 있으므로, 반드시 1 → 2 → ... → 3 → 4 순서대로 탐색한다.

2가 존재하는 경우, 마찬가지로 방문체크, MAP에 기록하고 rcData에도 값을 추가하고 queue에 넣는다.

	// 1 -> 2 찾기
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = r + dr[i];
		nc = c + dc[i];

		if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

		if (MAP[nr][nc].value == 2)
		{
			visit[nr][nc] = 1;
			MAP[nr][nc].loop = loop;
			MAP[nr][nc].order = order;

			rcData[loop][rcIndex[loop]].r = nr;
			rcData[loop][rcIndex[loop]].c = nc;
			rcData[loop][rcIndex[loop]].order = order++;
			rcData[loop][rcIndex[loop]++].number = 2;

			queue[wp].r = nr;
			queue[wp].c = nc;
			queue[wp++].number = 2;

			break;
		}	
	}

여기까지 찾은 사람의 수는 2가 된다. (1과 2)

rcPeople[loop] = 2; // 1, 2 count

이제 BFS 탐색을 하면서, 루프를 찾는다. (2 ~ 4의 값)

value가 0이 아니고 visit이 체크되지 않는 곳을 기록한다.

그리고 3 이하의 값인 경우 rcPeople을 증가하면 된다.

	while (wp > rp)
	{
		RC out = queue[rp++];
		
		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (MAP[nr][nc].value != 0 && visit[nr][nc] == 0)
			{
				visit[nr][nc] = 1;
				MAP[nr][nc].loop = loop;
				MAP[nr][nc].order = order;

				rcData[loop][rcIndex[loop]].r = nr;
				rcData[loop][rcIndex[loop]].c = nc;
				rcData[loop][rcIndex[loop]].order = order++;
				rcData[loop][rcIndex[loop]++].number = MAP[nr][nc].value;

				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].number = MAP[nr][nc].value;

				// 사람 수만 카운트
				if (MAP[nr][nc].value <= 3) rcPeople[loop]++;
			}
		}
	}

BFS 최종 코드는 다음과 같다.

void BFS(int r, int c, int loop, int visit[MAX][MAX])
{
	RC queue[MAX * MAX] = { 0 };
	int wp, rp, order;

	wp = rp = 0;
	order = 1;

	visit[r][c] = 1;
	MAP[r][c].loop = loop;
	MAP[r][c].order = order;

	rcData[loop][rcIndex[loop]].r = r;
	rcData[loop][rcIndex[loop]].c = c;
	rcData[loop][rcIndex[loop]].order = order++;
	rcData[loop][rcIndex[loop]++].number = 1;

	// 1 -> 2 찾기
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = r + dr[i];
		nc = c + dc[i];

		if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

		if (MAP[nr][nc].value == 2)
		{
			visit[nr][nc] = 1;
			MAP[nr][nc].loop = loop;
			MAP[nr][nc].order = order;

			rcData[loop][rcIndex[loop]].r = nr;
			rcData[loop][rcIndex[loop]].c = nc;
			rcData[loop][rcIndex[loop]].order = order++;
			rcData[loop][rcIndex[loop]++].number = 2;

			queue[wp].r = nr;
			queue[wp].c = nc;
			queue[wp++].number = 2;

			break;
		}
	}

	rcPeople[loop] = 2; // 1, 2 count 

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (MAP[nr][nc].value != 0 && visit[nr][nc] == 0)
			{
				visit[nr][nc] = 1;
				MAP[nr][nc].loop = loop;
				MAP[nr][nc].order = order;

				rcData[loop][rcIndex[loop]].r = nr;
				rcData[loop][rcIndex[loop]].c = nc;
				rcData[loop][rcIndex[loop]].order = order++;
				rcData[loop][rcIndex[loop]++].number = MAP[nr][nc].value;

				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].number = MAP[nr][nc].value;

				// 사람 수만 카운트
				if (MAP[nr][nc].value <= 3) rcPeople[loop]++;
			}
		}
	}
}

move 구현

모든 loop에 있는 사람을 움직이고, 점수를 계산해야 된다.

	for (int tc = 1; tc <= T; tc++)
	{
		...

		int score = 0;
		for (int k = 1; k <= K; k++) // round
		{
			// printMap(MAP);
			for (int m = 0; m < M; m++) move(m);

			score += getScore(k);

			// printMap(MAP);
		}

		printf("%d\n", score);
	}

움직이는 방향은 두 가지가 존재한다.

rcData는 (1, 2, ... 3, 4, ..., 4) 순서대로 좌표가 저장되어 있다.

기본 방향(direction = 0)은 머리사람(1)이 4로 이동하고, 맨 처음 2는 1로 이동하게 된다.

따라서 배열의 뒤부터 좌표를 이동하고, 마지막 4의 좌표는 tmp에 저장한 후, 1의 좌표에 저장하면 된다.

if (dir == 0) // 1 -> 4 -> .. -> 2 -> 1 위치로 이동
{
	tmp = rcData[loop][index - 1];

	for (int i = index - 2; i >= 0; i--)
	{
		int r = rcData[loop][i].r;
		int c = rcData[loop][i].c;

		rcData[loop][i + 1].r = r;
		rcData[loop][i + 1].c = c;
	}

	rcData[loop][0].r = tmp.r;
	rcData[loop][0].c = tmp.c;
}

공에 맞은 경우(direction 변경)는 반대로 구현하면 된다.

	else // 1 -> 2 -> 2 -> ... -> 3 -> 4 -> 1 위치로 이동
	{
		tmp = rcData[loop][0];

		for (int i = 1; i < index; i++)
		{
			int r = rcData[loop][i].r;
			int c = rcData[loop][i].c;

			rcData[loop][i - 1].r = r;
			rcData[loop][i - 1].c = c;
		}

		rcData[loop][index - 1].r = tmp.r;
		rcData[loop][index - 1].c = tmp.c;
	}

그리고 모든 좌표에 대해 MAP의 order와 number를 갱신한다.

for (int i = 0; i < index; i++)
{
	int r = rcData[loop][i].r;
	int c = rcData[loop][i].c;
	int order = rcData[loop][i].order;
	int number = rcData[loop][i].number;

	MAP[r][c].order = order;
	MAP[r][c].value = number;
}

전체 move 코드는 다음과 같다.

void move(int loop)
{
	RC tmp;
	int index = rcIndex[loop];
	int dir = direction[loop];

	// printf("loop %d dir %d\n", loop, dir);

	if (dir == 0) // 1 -> 4 -> .. -> 2 -> 1 위치로 이동
	{
		tmp = rcData[loop][index - 1];

		for (int i = index - 2; i >= 0; i--)
		{
			int r = rcData[loop][i].r;
			int c = rcData[loop][i].c;

			rcData[loop][i + 1].r = r;
			rcData[loop][i + 1].c = c;
		}

		rcData[loop][0].r = tmp.r;
		rcData[loop][0].c = tmp.c;
	}
	else // 1 -> 2 -> 2 -> ... -> 3 -> 4 -> 1 위치로 이동
	{
		tmp = rcData[loop][0];

		for (int i = 1; i < index; i++)
		{
			int r = rcData[loop][i].r;
			int c = rcData[loop][i].c;

			rcData[loop][i - 1].r = r;
			rcData[loop][i - 1].c = c;
		}

		rcData[loop][index - 1].r = tmp.r;
		rcData[loop][index - 1].c = tmp.c;
	}

	for (int i = 0; i < index; i++)
	{
		int r = rcData[loop][i].r;
		int c = rcData[loop][i].c;
		int order = rcData[loop][i].order;
		int number = rcData[loop][i].number;

		MAP[r][c].order = order;
		MAP[r][c].value = number;
	}
}

점수 계산하기

공을 던지면 사람 (1 ~ 3) 만 만나게 되므로 hit 배열을 만들어서 1, 2, 3 값만 판단하도록 한다.

int hit[] = { 0, 1, 1, 1, 0 };

라운드 별로 공을 던지는 방향과 라인(행 또는 열)이 다르다.

공을 던지는 방향을 0 ~ 3(→, ↑, ←, ↓)이라 하자.

	// → 1 ~ N ==> 0번 방향
	// ↑ N + 1 ~ 2 * N ==> 1번 방향
	// ← 2 * N + 1 ~ 3 * N ==> 2번 방향
	// ↓ 3 * N + 1 ~ 4 * N ==> 3번 방향

	// if N == 7 
	// → 1 ~ 7   
	// ↑ 8 ~ 14
	// ← 15 ~ 21
	// ↓ 22 ~ 28

N = 7인 경우 dir과 line은 아래와 같이 나와야 한다.

그리고 4 * N 만큼 반복된다.

round 1 : dir[0], line[1]
round 2 : dir[0], line[2]
round 3 : dir[0], line[3]
round 4 : dir[0], line[4]
round 5 : dir[0], line[5]
round 6 : dir[0], line[6]
round 7 : dir[0], line[7]

round 8 : dir[1], line[1]
round 9 : dir[1], line[2]
round 10 : dir[1], line[3]
round 11 : dir[1], line[4]
round 12 : dir[1], line[5]
round 13 : dir[1], line[6]
round 14 : dir[1], line[7]

round 15 : dir[2], line[1]
round 16 : dir[2], line[2]
round 17 : dir[2], line[3]
round 18 : dir[2], line[4]
round 19 : dir[2], line[5]
round 20 : dir[2], line[6]
round 21 : dir[2], line[7]

round 22 : dir[3], line[1]
round 23 : dir[3], line[2]
round 24 : dir[3], line[3]
round 25 : dir[3], line[4]
round 26 : dir[3], line[5]
round 27 : dir[3], line[6]
round 28 : dir[3], line[7]

round 29 : dir[0], line[1]
round 30 : dir[0], line[2]
...

라운드는 1 부터 입력된다고 가정하면 아래와 같은 식이 만들어진다. (라운드 반복 → 나머지 계산)

	int ballDir = (((round - 1) % (4 * N))) / N;
	int line = ((round - 1) % (N)) + 1;

실제 나머지 계산을 할 때, 값이 제대로 계산되는지 아래 예시 코드와 같이 출력해서 꼭 확인을 하자.

	int N = 7;
	for (int round = 1; round <= 100; round++)
	{
		int ballDir = (((round - 1) % (4 * N))) / N;
		int line = ((round - 1) % (N)) + 1;

		printf("round %d : dir[%d], line[%d]\n", round, ballDir, line);
	}

만약 → 방향으로 공을 던지는 경우, 행 row = line에 대해 col을 순차적으로 탐색해서

hit[ MAP[row][col] ]에 사람이 있는지 판단한다.

사람이 있는 경우 점수를 계산한다.

이때, 방향이 반대인 경우 머리사람과 꼬리사람이 바뀌므로

rcPeople에 저장한 전체 사람 수에 order를 빼고 1을 더해 순서를 바꾼다.

그리고 해당 값의 제곱을 return 한다.

if (ballDir == 0) // →
{
	for (int c = 1; c <= N; c++)
	{
		if (hit[MAP[line][c].value])
		{
			// printf("0 hit! %d %d [%d]\n", line, c, MAP[line][c].value);

			int loop = MAP[line][c].loop;
			int score = MAP[line][c].order;

			// 머리 꼬리 순서 변경
			if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

			direction[loop] = !direction[loop];

			return score * score;
		}
	}
}

방향이 ← 인 경우, 행의 아래에서 위로 공을 던진다.

따라서 line이 아니라 N + 1 - line으로 행을 탐색해야 한다.

방향이 ↓ 인 경우도 같은 처리를 한다. (전체 코드 참고)

	else if (ballDir == 2) // ←
	{
		for (int c = N; c >= 1; c--)
		{
			if (hit[MAP[N + 1 - line][c].value])
			{
				// printf("2 hit! %d %d [%d]\n", N + 1 - line, c, MAP[N + 1 - line][c].value);

				int loop = MAP[N + 1 - line][c].loop;
				int score = MAP[N + 1 - line][c].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}

전체 getScore 코드는 다음과 같다.

int getScore(int round)
{
	int hit[] = { 0, 1, 1, 1, 0 };

	// → 1 ~ N ==> 0번 방향
	// ↑ N + 1 ~ 2 * N ==> 1번 방향
	// ← 2 * N + 1 ~ 3 * N ==> 2번 방향
	// ↓ 3 * N + 1 ~ 4 * N ==> 3번 방향

	// if N == 7 
	// → 1 ~ 7   
	// ↑ 8 ~ 14
	// ← 15 ~ 21
	// ↓ 22 ~ 28

	int ballDir = (((round - 1) % (4 * N))) / N;
	int line = ((round - 1) % (N)) + 1;

	if (ballDir == 0) // →
	{
		for (int c = 1; c <= N; c++)
		{
			if (hit[MAP[line][c].value])
			{
				// printf("0 hit! %d %d [%d]\n", line, c, MAP[line][c].value);

				int loop = MAP[line][c].loop;
				int score = MAP[line][c].order;

				// 머리 꼬리 순서 변경
				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 1) // ↑
	{
		for (int r = N; r >= 1; r--)
		{
			if (hit[MAP[r][line].value])
			{
				// printf("1 hit! %d %d [%d]\n", r, line, MAP[r][line].value);

				int loop = MAP[r][line].loop;
				int score = MAP[r][line].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 2) // ←
	{
		for (int c = N; c >= 1; c--)
		{
			if (hit[MAP[N + 1 - line][c].value])
			{
				// printf("2 hit! %d %d [%d]\n", N + 1 - line, c, MAP[N + 1 - line][c].value);

				int loop = MAP[N + 1 - line][c].loop;
				int score = MAP[N + 1 - line][c].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 3) // ↓
	{
		for (int r = 1; r <= N; r++)
		{
			if (hit[MAP[r][N + 1 - line].value])
			{
				// printf("3 hit! %d %d [%d]\n", r, N + 1 - line, MAP[r][N + 1 - line].value);

				int loop = MAP[r][N + 1 - line].loop;
				int score = MAP[r][N + 1 - line].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}

	return 0;
}

전체 코드는 다음과 같다.

#include <stdio.h>

#define MAX (20 + 5)

int T;
int N, M, K;

typedef struct st1
{
	int value;
	int order;
	int loop;
}MAP_INFO;

MAP_INFO MAP[MAX][MAX];
int visit[MAX][MAX];

typedef struct st2
{
	int r;
	int c;
	int order;
	int number;
}RC;

RC rcData[5 + 2][MAX * MAX]; // 1, 2, 2, 3, 4, 4, 4, 4, 4, ... 의 좌표가 생성.
int rcIndex[5 + 2];
int rcPeople[5 + 2];
int direction[5 + 2];

int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
		{
			scanf("%d", &MAP[r][c].value);
			MAP[r][c].loop = MAP[r][c].order = -1;
		}
	}

	for (int i = 0; i < M; i++)
		rcIndex[i] = rcPeople[i] = direction[i] = 0;
}

void printVisit(int map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

void printMap(MAP_INFO map[MAX][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= N; c++)
			printf("%d ", map[r][c].value);
		putchar('\n');
	}
	putchar('\n');
}

void printRC(int loop)
{
	int index = rcIndex[loop];

	for (int i = 0; i < index; i++)
		printf("%d] (%d, %d) %d, %d\n", i, rcData[loop][i].r, rcData[loop][i].c, rcData[loop][i].order, rcData[loop][i].number);
	putchar('\n');
}

void BFS(int r, int c, int loop, int visit[MAX][MAX])
{
	RC queue[MAX * MAX] = { 0 };
	int wp, rp, order;

	wp = rp = 0;
	order = 1;

	visit[r][c] = 1;
	MAP[r][c].loop = loop;
	MAP[r][c].order = order;

	rcData[loop][rcIndex[loop]].r = r;
	rcData[loop][rcIndex[loop]].c = c;
	rcData[loop][rcIndex[loop]].order = order++;
	rcData[loop][rcIndex[loop]++].number = 1;

	// 1 -> 2 찾기
	for (int i = 0; i < 4; i++)
	{
		int nr, nc;

		nr = r + dr[i];
		nc = c + dc[i];

		if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

		if (MAP[nr][nc].value == 2)
		{
			visit[nr][nc] = 1;
			MAP[nr][nc].loop = loop;
			MAP[nr][nc].order = order;

			rcData[loop][rcIndex[loop]].r = nr;
			rcData[loop][rcIndex[loop]].c = nc;
			rcData[loop][rcIndex[loop]].order = order++;
			rcData[loop][rcIndex[loop]++].number = 2;

			queue[wp].r = nr;
			queue[wp].c = nc;
			queue[wp++].number = 2;

			break;
		}
	}

	rcPeople[loop] = 2; // 1, 2 count 

	while (wp > rp)
	{
		RC out = queue[rp++];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > N) continue;

			if (MAP[nr][nc].value != 0 && visit[nr][nc] == 0)
			{
				visit[nr][nc] = 1;
				MAP[nr][nc].loop = loop;
				MAP[nr][nc].order = order;

				rcData[loop][rcIndex[loop]].r = nr;
				rcData[loop][rcIndex[loop]].c = nc;
				rcData[loop][rcIndex[loop]].order = order++;
				rcData[loop][rcIndex[loop]++].number = MAP[nr][nc].value;

				queue[wp].r = nr;
				queue[wp].c = nc;
				queue[wp++].number = MAP[nr][nc].value;

				// 사람 수만 카운트
				if (MAP[nr][nc].value <= 3) rcPeople[loop]++;
			}
		}
	}
}

void move(int loop)
{
	RC tmp;
	int index = rcIndex[loop];
	int dir = direction[loop];

	// printf("loop %d dir %d\n", loop, dir);

	if (dir == 0) // 1 -> 4 -> .. -> 2 -> 1 위치로 이동
	{
		tmp = rcData[loop][index - 1];

		for (int i = index - 2; i >= 0; i--)
		{
			int r = rcData[loop][i].r;
			int c = rcData[loop][i].c;

			rcData[loop][i + 1].r = r;
			rcData[loop][i + 1].c = c;
		}

		rcData[loop][0].r = tmp.r;
		rcData[loop][0].c = tmp.c;
	}
	else // 1 -> 2 -> 2 -> ... -> 3 -> 4 -> 1 위치로 이동
	{
		tmp = rcData[loop][0];

		for (int i = 1; i < index; i++)
		{
			int r = rcData[loop][i].r;
			int c = rcData[loop][i].c;

			rcData[loop][i - 1].r = r;
			rcData[loop][i - 1].c = c;
		}

		rcData[loop][index - 1].r = tmp.r;
		rcData[loop][index - 1].c = tmp.c;
	}

	for (int i = 0; i < index; i++)
	{
		int r = rcData[loop][i].r;
		int c = rcData[loop][i].c;
		int order = rcData[loop][i].order;
		int number = rcData[loop][i].number;

		MAP[r][c].order = order;
		MAP[r][c].value = number;
	}
}

int getScore(int round)
{
	int hit[] = { 0, 1, 1, 1, 0 };

	// → 1 ~ N ==> 0번 방향
	// ↑ N + 1 ~ 2 * N ==> 1번 방향
	// ← 2 * N + 1 ~ 3 * N ==> 2번 방향
	// ↓ 3 * N + 1 ~ 4 * N ==> 3번 방향

	// if N == 7 
	// → 1 ~ 7   
	// ↑ 8 ~ 14
	// ← 15 ~ 21
	// ↓ 22 ~ 28

	int ballDir = (((round - 1) % (4 * N))) / N;
	int line = ((round - 1) % (N)) + 1;

	if (ballDir == 0) // →
	{
		for (int c = 1; c <= N; c++)
		{
			if (hit[MAP[line][c].value])
			{
				// printf("0 hit! %d %d [%d]\n", line, c, MAP[line][c].value);

				int loop = MAP[line][c].loop;
				int score = MAP[line][c].order;

				// 머리 꼬리 순서 변경
				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 1) // ↑
	{
		for (int r = N; r >= 1; r--)
		{
			if (hit[MAP[r][line].value])
			{
				// printf("1 hit! %d %d [%d]\n", r, line, MAP[r][line].value);

				int loop = MAP[r][line].loop;
				int score = MAP[r][line].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 2) // ←
	{
		for (int c = N; c >= 1; c--)
		{
			if (hit[MAP[N + 1 - line][c].value])
			{
				// printf("2 hit! %d %d [%d]\n", N + 1 - line, c, MAP[N + 1 - line][c].value);

				int loop = MAP[N + 1 - line][c].loop;
				int score = MAP[N + 1 - line][c].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}
	else if (ballDir == 3) // ↓
	{
		for (int r = 1; r <= N; r++)
		{
			if (hit[MAP[r][N + 1 - line].value])
			{
				// printf("3 hit! %d %d [%d]\n", r, N + 1 - line, MAP[r][N + 1 - line].value);

				int loop = MAP[r][N + 1 - line].loop;
				int score = MAP[r][N + 1 - line].order;

				if (direction[loop] == 1) score = rcPeople[loop] - score + 1;

				direction[loop] = !direction[loop];

				return score * score;
			}
		}
	}

	return 0;
}

int main(void)
{
	// scanf("%d", &T);
	T = 1;
	for (int tc = 1; tc <= T; tc++)
	{
		input();

		for (int r = 1; r <= N; r++)
			for (int c = 1; c <= N; c++)
				visit[r][c] = 0;

		int loop = 0;
		for (int r = 1; r <= N; r++)
		{
			for (int c = 1; c <= N; c++)
			{
				if (MAP[r][c].value == 1 && visit[r][c] == 0)
				{
					BFS(r, c, loop, visit);

					// printVisit(visit);
					// printRC(loop);

					loop++;
				}
			}
		}

		int score = 0;
		for (int k = 1; k <= K; k++) // round
		{
			// printMap(MAP);
			for (int m = 0; m < M; m++) move(m);

			score += getScore(k);

			// printMap(MAP);
		}

		printf("%d\n", score);
	}

	return 0;
}