상경한 개발자 지망생들

문제 링크

https://www.acmicpc.net/problem/16236

접근 방법

문제를 읽다가 '거리는 아기 상어가 있는 칸에서 물고기가 있는 칸으로 이동할 때, 지나야하는 칸의 개수의 최솟값이다.부분과 더 큰 물고기는 지나갈 수 없다는 조건에서 BFS 알고리즘의 문제라는 것을 깨닫고, BFS로 문제 풀이를 시작했다. 풀다보니 전형적인 BFS의 형식에 귀찮은 조건이 몇 가지 추가된 꼴이었다.

소스 코드

코드에 주석을 많이 남겨놨습니다. :) 복잡한 계산이 있는 문제가 아니니, 코드로 참고 부탁드려요!

#include <queue>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 21
#define NUM_DIRECTION 4
using namespace std;
typedef struct coord {
	int y, x, size, time;
};
int N, map[MAX][MAX], visit[MAX][MAX], expp = 0;
coord shark; // 아기 상어의 좌표 및 크기
// vector<coord> fishs; // 물고기들의 좌표 및 크기
vector<coord> eatable_fishs;
const coord direction[NUM_DIRECTION] = { {0, 1, 0, 0}, {0, -1, 0, 0}, {1, 0, 0, 0}, {-1, 0, 0, 0} };

bool comp(const coord& a1, const coord& b1) {
	if (a1.time == b1.time) { // 시간이 동일하다면, y가 작은 순으로
		if (a1.y == b1.y) { // y도 동일하다면 x가 작은 순으로
			return a1.x < b1.x;
		}
		return a1.y < b1.y;
	}
	return a1.time < b1.time; // 시간이 작은 순으로
}

bool isRanged(int y, int x) {
	if (y >= N || x >= N || y < 0 || x < 0) return false;
	return true;
}

void search_eatable() {
	queue<coord> q;
	memset(visit, 0, sizeof(visit)); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	eatable_fishs.clear(); // 현재 위치에서 시간 계산을 다시 해야하므로 초기화
	visit[shark.y][shark.x] = 1;
	q.push(shark);
	coord cur;
	int ny, nx;
	while (!q.empty()) {
		cur = q.front();
		q.pop();
		for (int i = 0; i < NUM_DIRECTION; ++i) {
			ny = cur.y + direction[i].y;
			nx = cur.x + direction[i].x;
			if (isRanged(ny, nx) && !visit[ny][nx] && map[ny][nx] <= shark.size) { 
				// 범위 내에 있고, 방문하지 않았으며, 지나가야 하므로 크기가 더 작다면
				if (map[ny][nx] != 0 && shark.size > map[ny][nx])
					// 먹을 수 있는 물고기라면? 물고기 백터에 넣음
					eatable_fishs.push_back({ ny, nx, map[ny][nx], cur.time + 1 });
				visit[ny][nx] = 1;
				q.push({ ny, nx, 0, cur.time + 1 });
			}
		}
	}
}

// 경험치를 체크하여 사이즈와 같아졌다면 사이즈업, 경험치 초기화
void check_exp() {
	if (expp >= shark.size) {
		++shark.size;
		expp = 0;
	}
}

// eatable_fish의 물고기를 먹고, 해당 자리로 이동하며, 소요된 시간을 반환한다.
int move_and_eat(coord eatable_fish) {
	map[shark.y][shark.x] = 0; // 자리를 비운다.
	map[eatable_fish.y][eatable_fish.x] = 9; // 먹어치운 물고기의 좌표로 이동한다.
	shark.y = eatable_fish.y;
	shark.x = eatable_fish.x;
	++expp; // 경험치 +1
	check_exp();
	return eatable_fish.time;
}

int solve() {
	int ret = 0;
	while (1) {
		search_eatable(); // 현재 위치에서 물고기들과의 거리 및 크기 계산
		if (!eatable_fishs.empty()) { // 먹을 수 있는 물고기가 존재한다면
			sort(eatable_fishs.begin(), eatable_fishs.end(), comp); // 좌표 순으로 정렬
			ret += move_and_eat(eatable_fishs.front()); // 가장 가까운 물고기를 먹는다.
		}
		else // 먹을 수 있는 물고기가 존재하지 않는다면
			break;
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	memset(visit, 0, sizeof(visit));
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			cin >> map[i][j];
			if (map[i][j] != 0) { // 빈 칸이 아니라면
				if (map[i][j] == 9) { // 아기 상어라면
					shark.y = i;
					shark.x = j;
					shark.size = 2; // 초기 크기 = 2(조건)
					shark.time = 0;
				}
			}
		}
	}
	cout << solve();
	return 0;
}

개발 환경은 VS2019입니다.

질문, 지적, 덧글 환영합니다!

문제 링크

https://www.acmicpc.net/problem/14499

접근 방법

복잡한 알고리즘성 문제가 아닌 시뮬레이션 문제였습니다.

주사위를 4가지 방향으로 굴렸을때 각 면의 값이 어떻게 이동하는지 그림을 그려보면서 접근하였고, 매번 이동을 진행하기 전에 좌표에 대한 검사를 진행하였습니다. dice[6] 배열을 선언하여 주사위의 각면에 번호를 매겨서 접근하였지만, 번호로 보니 햇갈려서 각 번호 면에 대하여 참조 변수를 알아보기 쉽게 선언하였습니다.

아래와 같이 각 면을 참조한 뒤, 설명대로 주사위를 움직입니다. 움직일 때 마다 주사위의 면의 값 뿐만 아니라, 좌표 이동도 해줍니다.

int& north = dice[0],

west = dice[1], 

top = dice[2], 

east = dice[3], 

south = dice[4], 

bot = dice[5];

이동이 끝난 뒤에는 현재 위치의 지도값이 0인지, 0이 아닌지에 따라 다른 처리를 해주었고, 만약 이동할 수 없는 경우 함수 자체에서 false를 반환하였고, 이동이 성공한 경우 true를 반환하여 지도값에 따른 처리를 해주었습니다.

처음에 입력으로 주는 주사위의 초기 위치를 x, y 거꾸로 받아서 한참을 해맸는데, 아마 이 부분 실수하는 분들이 많을 것 같습니다.

소스 코드

#include <cstring>
#include <iostream>
#define MAX 21
#define MAXK 1001
#define NUMD 5
#define NUM_DICE 6
using namespace std;
typedef struct coord {
	int y, x;
};
int N, M, K, map[MAX][MAX], cmd[MAXK];
coord cur;
int dice[6];
const coord direction[NUMD] = { {0, 0}, {0, 1}, {0, -1}, {-1, 0}, {1, 0} }; // 0, 동, 서, 북, 남
int& north = dice[0], west = dice[1], top = dice[2], east = dice[3], south = dice[4], bot = dice[5];

// 0 = north
// 1 = west
// 2 = top
// 3 = east
// 4 = south
// 5 = bot

bool isRanged(int y, int x) {
	if (y >= N || x >= M || y < 0 || x < 0) return false;
	return true;
}

bool move_dice(int d) {
	int ny, nx;
	int temp;
	ny = cur.y + direction[d].y;
	nx = cur.x + direction[d].x;
	if (!isRanged(ny, nx)) return false;
	if (d == 1) { // 동
		temp = east;
		east = top;
		top = west;
		west = bot;
		bot = temp;
	}
	else if (d == 2) { // 서
		temp = west;
		west = top;
		top = east;
		east = bot;
		bot = temp;
	}
	else if (d == 3) { // 북
		temp = north;
		north = top;
		top = south;
		south = bot;
		bot = temp;
	}
	else { // 남
		temp = bot;
		bot = south;
		south = top;
		top = north;
		north = temp;
	}
	cur.y = ny;
	cur.x = nx;
	return true;
}

void solve() {
	for (int k = 0; k < K; ++k) {
		if (move_dice(cmd[k])) { // 움직였다면
			if (map[cur.y][cur.x] == 0) { // 지도칸이 0이라면
				map[cur.y][cur.x] = bot;
			}
			else { // 지도칸이 0이 아니라면, 칸의 수가 주사위 바닥으로 복사, 칸은 0
				bot = map[cur.y][cur.x];
				map[cur.y][cur.x] = 0;
			}
			cout << top << "\n";
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M >> cur.y >> cur.x >> K;
	memset(dice, 0, sizeof(dice));
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
			cin >> map[i][j];
	for (int k = 0; k < K; ++k) cin >> cmd[k]; // 1: 동, 2: 서, 3: 북, 4: 남
	solve();
	return 0;
}

개발 환경은 VS 2019입니다.

질문, 지적 환영합니다. 감사합니다!!

문제 링크

https://www.acmicpc.net/problem/11066

접근 방법

처음에는 정말 단순하게 오름차순으로 정렬해서 크기순으로 합치는 접근법을 사용했으나, 오답이 나왔습니다.

여러 블로그를 참고하여 인접한 파일끼리 합친다는 접근 방법을 적용하여 분할 정복 + DP 느낌으로 풀었습니다.

소스 코드

MAX를 501로 두고, SUM[0] = 0으로 두었습니다.

sum[a] = 0 ~ 파일 a까지의 비용의 합입니다.

cache[a][b] = 구간 [a, b]를 합치는데 드는 최소 비용입니다.

따라서 cache[a][a] = 0입니다. (합칠 구간이 없으므로)

cache[a][a+1] = sum[a + 1] - sum[a - 1]입니다.

cache[a][a + 2] = min(cache[a][a] + cache[a+1][a+2], cache[a][a+1] + cache[a+2][a+2]) + sum[a+2] - sum[a] 입니다.

더 큰 구간에 대한 문제는

cache[a][b] = min(cache[a][b], cache[a][a+mid] + cache[mid+1][b])에서 mid를 a부터 b - 1까지 반복함으로써 최소 비용을 구합니다. ( a <= b )

#include <climits>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 501
using namespace std;
int sum[MAX], cache[MAX][MAX], cost[MAX];

int divide(int low, int high) {
	if (low >= high) return 0;
	int& ret = cache[low][high];
	if (ret != -1) return ret;
	ret = INT_MAX;
	for (int mid = low; mid < high; ++mid) {
		ret = min(ret, divide(low, mid) + divide(mid + 1, high) + sum[high] - sum[low - 1]);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int T, K;
	cin >> T;
	for (int t = 0; t < T; ++t) {
		cin >> K;
		memset(sum, 0, sizeof(sum));
		memset(cache, -1, sizeof(cache));
		sum[0] = 0;
		for (int i = 1; i <= K; ++i) {
			cin >> cost[i];
			sum[i] = sum[i - 1] + cost[i];
		}
		cout << divide(1, K) << "\n";
	}
	return 0;
}

Visual Studio 2019 사용하였습니다.

질문, 지적 환영입니다!