[CodeTree] 삼성 코테 준비 - 놀이기구 탑승

1. 문제 출처

https://www.codetree.ai/frequent-problems/go-on-the-rides/description

코드트리

 

2. 문제 풀이

문제에 설명되어 있는 조건을 따라 코드를 구현해주면 되는 Simulation 문제임.

놀이기구 탑승자들의 최적 위치 탐색은 완전 탐색으로 구현.

#include <iostream>
#include <vector>

using namespace std;

#define MAX_N 20

int n;
int num_of_people; // n*n
int map[MAX_N][MAX_N];
int friends[400][5]; //친한 친구 정보 저장

int dr[4] = {-1, 1, 0, 0}; // u d l r
int dc[4] = {0, 0, -1, 1};

int score[5] = {0, 1, 10, 100, 1000}; // 0, 1, 2, 3, 4
int answer = 0;

void Input() {
	cin >> n;

	num_of_people = n * n;
	int num;
	for (int i = 0; i < num_of_people; i++) {
		for (int k = 0; k < 5; k++) {
			cin >> num;
			friends[i][k] = num;
		}
	}
}
bool InRange(int new_r, int new_c) {
	return new_r >= 0 && new_r < n&& new_c >= 0 && new_c < n;
}
void Simulation() {
	for (int i = 0; i < num_of_people; i++) {
		int cur_std = friends[i][0]; //map에 위치 지정해줄 현재 순서의 사람
		int blank = 0; //최적이라 판단되는 위치의 주변 빈 공간 개수
		int nf = 0; //최적이라 판단되는 위치의 주변 친구 수
		int cr = MAX_N + 1, cc = MAX_N + 1; //최적이라 판단되는 위치

		for (int r = 0; r < n; r++) { // map 전체를 완전 탐색으로 서치
			for (int c = 0; c < n; c++) {
				if (map[r][c] != 0) continue;

				int new_blank=0;
				int new_nf=0;
				int new_r = 0;
				int new_c = 0;

				for (int d = 0; d < 4; d++) { //현재 위치에서 상하좌우 조건 확인
					new_r = r + dr[d];
					new_c = c + dc[d];
					if (InRange(new_r, new_c)) {
						if (map[new_r][new_c] == 0) { //빈공간 확인
							new_blank++;
						}
						else {
							for (int f = 1; f < 5; f++) { //친구 확인
								if (map[new_r][new_c] == friends[i][f]) {
									new_nf++;
									break;
								}
							}
						}
					}
				}
                // 최적 위치 조건 확인
				if (new_nf > nf) {
					nf = new_nf;
					blank = new_blank;
					cr = r;
					cc = c;					
				}
				else if (new_nf == nf) {
					if (new_blank > blank) {
						blank = new_blank;
						cr = r;
						cc = c;
					}
					else if (new_blank == blank) {
						if (r < cr) {
							cr = r;
							cc = c;
						}
						else if (r == cr && c < cc) {
							cc = c;
						}
					}
				}
			}
		}
		map[cr][cc] = cur_std;
	}
}
void CountScore() {
	for (int r = 0; r < n; r++) {
		for (int c = 0; c < n; c++) {
			int num = 0;
			for (int current = 0; current < num_of_people; current++) {
				if (map[r][c] == friends[current][0]) {
					for (int d = 0; d < 4; d++) {
						if (InRange(r + dr[d], c + dc[d])) {
							for (int f = 1; f < 5; f++) {
								if (map[r + dr[d]][c + dc[d]] == friends[current][f]) num++;
							}
						}
					}

					break;
				}
			}
			answer += score[num];
		}
	}

	cout << answer << endl;
}
int main(void) {
	cin.sync_with_stdio(0);
	cin.tie(NULL);

	Input();
	Simulation();
	CountScore();

	return 0;
}

3. 코드트리 풀이

코드트리는 문제 별 코드를 올려줘서 문제 풀고 난 후에 stl이나 문제에 대한 접근 방법 등을 공부하기에 좋음.

코드를 보면 

• tuple을 이용한 조건 비교 간소화 
• 친한 친구 정보를 bool type의 이차원 배열에 저장하여 친한 친구 찾을 때마다 인덱스로 접근함
• 하나의 함수에 모든 것을 구현하지 않고 function 별로 나누어 코딩