문제 링크

삼성 코딩테스트 기출 문제: 코드트리 빵 - 코드트리

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

코드트리

문제 설명

빵을 구하고자 하는 사람은 m명이 있는데, m번 사람이 m분에 각자의 베이스 캠프에서 출발하여 펀의점으로 이동함. 출발 시간이 되기 전 격자 밖에 나와있으며, 사람들이 목표하는 편의점이 모두 다름. n*n 크기 격자 위에서 진행됨.

1. 격자에 있는 사람들 모두가 본인이 원하는 편의점을 향해서 1칸 움직임. 최단거리로 움직이며 (상하좌우)의 우선순위로 움직이게 됨.
2. 편의점에 도달하면 해당 편의점에 멈추게 되고, 다른 사람들은 해당 편의점을 지날 수 없음. 격자에 있는 사람들이 모두 이동한 뒤에 해당 칸을 지날 수 없어짐.
3. t분에 해당하는 사람이 자신이 가고 싶은 가장 가까운 베이스캠프로 들어감. 여러 개라면, 행-열이 작은 순으로 베이스캠프를 선택함. 해당 베이스캠프는 다른 사람들이 지날 수 없게 됨.

해결 방법

1. 격자에 있는 사람들이 움직임

int e = t > m ? m : t;
for (int i = 0;i < e;i++) {
	if (info[i].finished) continue;
	runner_move(i);
}

void runner_move(int t) {
	int cx, cy, nx, ny;
	cx = info[t].rx, cy = info[t].ry;

	int d = -1;
	int cur_dist = INT_MAX;

	int next_dist;
	for (int i = 0;i < 4;i++) {
		nx = cx + dx[i], ny = cy + dy[i];
		if (nx < 0 || ny < 0 || ny >= n || ny >= n) continue;
		if (rock[nx][ny]) continue;
		next_dist = get_distance(nx, ny, t);
		if (next_dist < cur_dist) {
			d = i;
			cur_dist = next_dist;
		}
	}

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

	info[t].rx += dx[d], info[t].ry += dy[d];
}

1. 편의점에 도달하면 멈추고 다른 사람들이 지날 수 없게 하기

for (int i = 0;i < e;i++) {
	if (info[i].finished) continue;
	if (info[i].rx == info[i].dx && info[i].ry == info[i].dy) {
		info[i].finished = true;
		rock[info[i].dx][info[i].dy] = 1;
		chk++;
	}
}

1. t분에 해당하는 사람이 베이스캠프를 선택

void push_people(int t) {
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> que;
	que.push({ info[t].dx,info[t].dy });
	visited[info[t].dx][info[t].dy] = 1;

	int cx, cy, nx, ny;
	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] || rock[nx][ny]) continue;
			visited[nx][ny] = visited[cx][cy] + 1;
			que.push({ nx,ny });
		}
	}

	int cur_dist = INT_MAX;
	int x, y;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (visited[i][j] == 0 || camp[i][j] == 0) continue;
			if (cur_dist > visited[i][j]) {
				cur_dist = visited[i][j];
				x = i, y = j;
			}
		}
	}

	// 예외처리
	if (cur_dist == INT_MAX) {
		cout << "error";
		exit(0);
	}

	info[t].rx = x, info[t].ry = y;
	rock[x][y] = 1;
}

전체 코드

#include <iostream>
#include <cstring>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;

typedef struct {
	int dx, dy;
	int rx, ry;
	bool finished;
}_info;

int n, m;
int camp[16][16];
int rock[16][16];
int visited[16][16];
_info info[31];

int chk = 0;

void input() {
	cin >> n >> m;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cin >> camp[i][j];
		}
	}

	for (int i = 0;i < m;i++) {
		cin >> info[i].dx >> info[i].dy;
		info[i].dx--, info[i].dy--;
		info[i].finished = false;
	}
}

int dx[4] = { -1,0,0,1 };
int dy[4] = { 0,-1,1,0 };

void push_people(int t) {
	memset(visited, 0, sizeof(visited));
	queue<pair<int, int>> que;
	que.push({ info[t].dx,info[t].dy });
	visited[info[t].dx][info[t].dy] = 1;

	int cx, cy, nx, ny;
	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] || rock[nx][ny]) continue;
			visited[nx][ny] = visited[cx][cy] + 1;
			que.push({ nx,ny });
		}
	}

	int cur_dist = INT_MAX;
	int x, y;
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (visited[i][j] == 0 || camp[i][j] == 0) continue;
			if (cur_dist > visited[i][j]) {
				cur_dist = visited[i][j];
				x = i, y = j;
			}
		}
	}

	// 예외처리
	if (cur_dist == INT_MAX) {
		cout << "error";
		exit(0);
	}

	info[t].rx = x, info[t].ry = y;
	rock[x][y] = 1;
}

int get_distance(int x, int y, int t) {
	int ex, ey;
	ex = info[t].dx, ey = info[t].dy;

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

	int cx, cy, nx, ny;
	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] || rock[nx][ny]) continue;
			visited[nx][ny] = visited[cx][cy] + 1;
			que.push({ nx,ny });
		}
	}

	if (visited[ex][ey] == 0) return INT_MAX;
	return visited[ex][ey];
}

void runner_move(int t) {
	int cx, cy, nx, ny;
	cx = info[t].rx, cy = info[t].ry;

	int d = -1;
	int cur_dist = INT_MAX;

	int next_dist;
	for (int i = 0;i < 4;i++) {
		nx = cx + dx[i], ny = cy + dy[i];
		if (nx < 0 || ny < 0 || ny >= n || ny >= n) continue;
		if (rock[nx][ny]) continue;
		next_dist = get_distance(nx, ny, t);
		if (next_dist < cur_dist) {
			d = i;
			cur_dist = next_dist;
		}
	}

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

	info[t].rx += dx[d], info[t].ry += dy[d];
}

void solve(int t) {
	int e = t > m ? m : t;
	for (int i = 0;i < e;i++) {
		if (info[i].finished) continue;
		runner_move(i);
	}

	for (int i = 0;i < e;i++) {
		if (info[i].finished) continue;
		if (info[i].rx == info[i].dx && info[i].ry == info[i].dy) {
			info[i].finished = true;
			rock[info[i].dx][info[i].dy] = 1;
			chk++;
		}
	}

	if (t < m) {
		push_people(t);
	}
}

void print_map(int t) {
	int tmp_arr[50][50];
	memset(tmp_arr, 0, sizeof(tmp_arr));
	int e = t > m ? m : t;
	for (int i = 0;i <= e;i++) {
		tmp_arr[info[i].rx][info[i].ry] = i + 1;
	}

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			cout << tmp_arr[i][j] << " ";
		}
		cout << "\\n";
	}
	cout << "\\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("sample_input.txt", "r", stdin);
	input();
	for (int t = 0;;t++) {
		solve(t);
//		print_map(t);
		if (chk >= m) {
			cout << t + 1;
			break;
		}
	}
}