문제 링크

삼성 코딩테스트 기출 문제: 꼬리잡기놀이 - 코드트리

주요 IT 기업의 코딩테스트 기출 문제를 연습하며 실전 감각을 키우세요. 취업 합격률을 높이는 필수 연습 과정입니다.

코드트리

문제 설명

n*n 격자에 꼬리잡기 게임을 함. 3명 이상이 한 팀이 되고, 맨 앞 사람이 머릿사람, 맨 뒤 사람이 꼬리사람임. 각 팀은 주어진 이동 선을 따라서만 이동하고, 이동 선은 끝이 이어져 있음.

1. 먼저 각 팀은 한 칸 이동함
2. 각 라운드마다 공이 정해진 선에 따라 던져짐. 좌-하-우-상… 이런 순으로 던져지는데 자세한 건 문제 참고
3. 공이 사람에 맞으면 머리 사람을 시작으로 k번째 사람이라면 k의 제곱만큼 점수를 얻음.

점수의 총 합을 구하기

해결 방법

1. 각 꼬리잡기 그룹들을 저장머릿사람을 기준으로 시작해서 이동 선을 저장해줌. 이동선의 크기 만큼 인원들이 있을 수도 있음을 주의해야 함. 이 코드에서는 3명 이상이 팀이 되는 점을 간과했는데, 머리일때는 2만 찾게 해주면 될 것 같음.

typedef struct {
	vector<pair<int, int>> line;
	int cur; // 머리의 위치
	bool is_reverse;
	int cnt; // 사람 인원
}_group;

vector<_group> group;
int group_cnt = 0;

void get_count(int x,int y,int cur) {
	int cx, cy, nx, ny;
	int cnt = 0;

	// 만약 머리나 꼬리가 아닌 사람이 없는 두명인 선이라면
	bool just_two = true;
	for (int i = 0;i < 4;i++) {
		nx = x + dx[i], ny = ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
		if (arr[nx][ny] == 2) {
			just_two = false;
			break;
		}
	}

	// 만약 꽉 찬 선이라면
	bool not_full = true;
	int tmp_cnt = 0;
	for (int i = 0;i < 4;i++) {
		nx = x + dx[i], ny = ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
		if (arr[nx][ny] == 3 || arr[nx][ny] == 1) {
			tmp_cnt++;
			break;
		}
	}
	if (tmp_cnt >= 2) {
		not_full = false;
	}

	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> que;
	que.push({ x,y });
	visited[x][y] = 1;
	line_arr[x][y] = cur + 1;

	vector<pair<int, int>> line;
	line.push_back({ x,y });
	while (!que.empty()) {
		tie(cx, cy) = que.front();
		que.pop();
		for (int i = 0;i < 4;i++) {
			nx = cx + dx[i], ny = cy + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
			if (visited[nx][ny]) continue;
			if (arr[nx][ny] == 0) continue;
			if (!just_two && arr[cx][cy] == 1 && arr[nx][ny] == 4) continue;
			if (not_full && arr[cx][cy] == 1 && arr[nx][ny] == 3) continue;
			visited[nx][ny] = 1;
			que.push({ nx,ny });
			line.push_back({ nx,ny });
			line_arr[nx][ny] = cur + 1;
			break;
		}
	}

	for (int i = 0;i < line.size();i++) {
		cx = line[i].first, cy = line[i].second;
		if (arr[cx][cy] == 4) break;
		cnt++;
	}

	_group tmp;
	tmp.line = line;
	tmp.cnt = cnt;
	tmp.is_reverse = false;
	tmp.cur = 0;
	group.push_back(tmp);
}

void init() {
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (arr[i][j] == 1) {
				get_count(i,j,group_cnt);
				group_cnt++;
			}
		}	
	}
}

1. 각 팀 한 칸 씩 이동

for (int i = 0;i < group_cnt;i++) {
	group_move(i);
}
...

void group_move(int cur) {
	int group_size = group[cur].line.size();
	int head_cur = group[cur].cur;
	bool is_reverse = group[cur].is_reverse;

	if (is_reverse) {
		group[cur].cur = (head_cur + 1) % group_size;
	}
	else {
		if (head_cur == 0) group[cur].cur = group_size - 1;
		else group[cur].cur = head_cur - 1;

	}
}

1. 공에 맞는지 확인을 위한 배열에 꼬리잡기 그룹들 그려주기

memset(draw_arr, 0, sizeof(draw_arr));
for (int i = 0;i < group_cnt;i++) {
	draw_group(i);
}
...

void draw_group(int cur) {
	int x, y;
	int idx = group[cur].cur;
	int group_size = group[cur].line.size();
	bool is_reverse = group[cur].is_reverse;
	for (int i = 0;i < group[cur].cnt;i++) {
		x = group[cur].line[idx].first, y = group[cur].line[idx].second;
		draw_arr[x][y] = cur + 1;
		if (is_reverse) {
			if (idx == 0) idx = group_size - 1;
			else idx--;
		}
		else {
			idx = (idx + 1) % group_size;
		}
	}
}

1. 공 던지기

int check = cur % (n * 4);
int idx = check % n;
if (check >= 0 && check <= n-1) {
	for (int i = 0;i < n;i++) {
		if (draw_arr[idx][i] != 0) {
			get_point(draw_arr[idx][i], idx, i);
			break;
		}
	}
}
else if (check >= n && check <= n * 2 - 1) {
	for (int i = n-1;i >= 0;i--) {
		if (draw_arr[i][idx] != 0) {
			get_point(draw_arr[i][idx], i, idx);
			break;
		}
	}
}
else if (check >= 2 * n && check <= 3 * n - 1) {
	idx = n - idx - 1;
	for (int i = n-1;i >= 0;i--) {
		if (draw_arr[idx][i] != 0) {
			get_point(draw_arr[idx][i], idx, i);
			break;
		}
	}
}
else {
	idx = n - idx - 1;
	for (int i = 0;i < n;i++) {
		if (draw_arr[i][idx] != 0) {
			get_point(draw_arr[i][idx], i, idx);
			break;
		}
	}
}

1. 공을 맞았을 경우 점수 올려주기

void get_point(int cur,int c_x,int c_y) {
	cur--;
	// 몇번째인지 확인
	int x, y;
	int idx = group[cur].cur;
	int group_size = group[cur].line.size();
	bool is_reverse = group[cur].is_reverse;

	int target_idx = -1;
	int tail_idx = -1;

	for (int i = 0;i < group[cur].cnt;i++) {
		x = group[cur].line[idx].first, y = group[cur].line[idx].second;
		if (c_x == x && c_y == y) {
			// 발견
			target_idx = i;
		}
		if (i != group[cur].cnt - 1) {
			if (is_reverse) {
				if (idx == 0) idx = group_size - 1;
				else idx--;
			}
			else {
				idx = (idx + 1) % group_size;
			}
		}
	}

	if (target_idx == -1) {
		cout << "error!\\n";
		exit(0);
	}

	result += (target_idx + 1) * (target_idx + 1);

	group[cur].is_reverse = !(group[cur].is_reverse);
	group[cur].cur = idx;

	return;
}