SW 역량테스트 - [백준] 아기 상어 문제 풀이/해답/코드 (C++ / JAVA)

---

SW 역량 테스트 준비를 위한 핵심 문제들을 다룹니다!

해답을 보기 전에 문제를 풀어보시거나, 설계를 하고 오시는 것을 추천드립니다. 

코드에 대한 설명은 주석을 참고해 주세요 :)

 

---

문제 링크 : www.acmicpc.net/problem/16236

해답 코드 : 

 

#include <iostream>
#include <deque>

using namespace std;

typedef struct pos {

	int row;
	int col;

}pos;

typedef struct route {

	int row;
	int col;
	int dist;

} route;

typedef struct shark {

	int row;
	int col;
	int s_size;
	int feed;

}shark;


int N;
int map[20][20];

shark baby;
int ans_sec;

int dR[4] = {-1, 1, 0, 0};
int dC[4] = {0, 0, -1, 1};

deque<pos> food;

void eat(pos fish) {

	baby.feed++;

	if (baby.feed == baby.s_size) {
		
		if (baby.s_size < 8) baby.s_size++;
		baby.feed = 0;
	}

	// empty original position
	map[baby.row][baby.col] = 0;

	// move
	map[fish.row][fish.col] = 9;
	baby.row = fish.row;
	baby.col = fish.col;
}

bool isRange(int row, int col) {
	if (row < 0 || row >= N || col < 0 || col >= N) {
		return false;
	}
	else {
		return true;
	}
}

// prioritize "Up" and "Left"
route prior_pos(route A, route B) {

	if (A.row < B.row) {
		return A;
	}
	else if (A.row == B.row && A.col < B.col) {
		return A;
	}
	else {
		return B;
	}

}

// return minimum distance from st to end
route bfs_dist(pos st) {

	route t_pos;
	route n_pos;
	bool visited[20][20] = { false };

	int n_r, n_c;
	deque<route> myQ;
	int min_dist = 99999;

	// compare route with same distance
	deque<route> prior_q;

	t_pos = { st.row, st.col, 0 };
	visited[t_pos.row][t_pos.col] = true;
	myQ.push_front(t_pos);

	while (!myQ.empty()) {

		// visit
		t_pos = myQ[0];
		if (t_pos.dist > min_dist) {
			break;
		}

		// terminator
		if (map[t_pos.row][t_pos.col] < baby.s_size && map[t_pos.row][t_pos.col] != 0) {
			min_dist = t_pos.dist;
			prior_q.push_back(t_pos);
			myQ.pop_front();
			continue;
		}

		for (int i = 0; i < 4; i++) {

			n_r = t_pos.row + dR[i];
			n_c = t_pos.col + dC[i];

			// check move condition
			if (isRange(n_r, n_c) && !visited[n_r][n_c] && map[n_r][n_c] <= baby.s_size) {
				n_pos = {n_r, n_c, t_pos.dist+1};
				visited[n_r][n_c] = true;
				myQ.push_back(n_pos);
			}
		}

		myQ.pop_front();
	}

	if (!prior_q.empty()) {
		t_pos = prior_q[0];	
		
		for (int i = 0; i < prior_q.size(); i++) {
			t_pos = prior_pos(t_pos, prior_q[i]);
		}

		return t_pos;
	}


	// if there is no route
	t_pos = {-1, -1, 99999};
	return t_pos;
}


// check three cases
int shark_move() {

	route min_route;

	pos start = {baby.row, baby.col};
	pos target;

	// push possible fish to the food vector
	min_route = bfs_dist(start);

	if (min_route.dist >= 99999) {
		return -1;
	}
	else {
		target = {min_route.row, min_route.col};
		eat(target);
		ans_sec += min_route.dist;
		
		return 1;
	}

}

int main() {
	
	cin >> N;
	
	ans_sec = 0;


	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {

			cin >> map[i][j];

			if (map[i][j] == 9) {
				baby = {i, j, 2, 0};
			}

		}
	}

	while (shark_move() != -1) {
		;
	}


	cout << ans_sec << endl;

}

 

 

SW 역량테스트 준비 - [모의 SW 역량테스트] 풀이 / 코드 / 답안 (C++ / JAVA)

SW 역량테스트 준비 - C++ 코드, Java 코드

SW 역량테스트 준비 - 백준 알고리즘 문제