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

---

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

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

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

 

---

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

해답 코드 : 

 

#include <iostream>
#include <vector>

using namespace std;

typedef struct fish {

	int num;
	int dir;

}fish;

typedef struct pos {

	int row;
	int col;
	int alive; // 0 = dead

}pos;

fish map[4][4];
fish shark;
pos fish_pos[17]; // 0 is not used

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

int ans;

bool isRange(int r, int c) {
	if (r < 0 || r >= 4 || c < 0 || c >= 4) {
		return false;
	}
	else return true;
}

void swap(fish &a, fish &b) {
	fish temp = a;
	a = b;
	b = temp;
}

void swap_pos(pos &a, pos &b) {
	pos temp = a;
	a = b;
	b = temp;
}

void fish_move() {

	fish t_fish;
	int n_r, n_c, n_d;
	int r, c;
	pos move_it;

	for (int i = 1; i <= 16; i++) {

		move_it = fish_pos[i];
		r = move_it.row;
		c = move_it.col;

		if (move_it.alive != 0) {

			t_fish = map[r][c];

			// if it is a fish
			if (t_fish.num >= 1 && t_fish.num <= 16) {

				for (int d = 0; d < 8; d++) {

					n_d = (t_fish.dir + d) % 8;
					//map[r][c].dir = n_d;

					n_r = r + dR[n_d];
					n_c = c + dC[n_d];

					if (!isRange(n_r, n_c) || map[n_r][n_c].num == 100) {
						continue;
					}

					if (map[n_r][n_c].num == 0) {
						map[n_r][n_c] = { t_fish.num, n_d };
						map[r][c].num = 0;
						fish_pos[i] = { n_r, n_c, 1};
						break;
					}

					if (map[n_r][n_c].num >= 1 && map[n_r][n_c].num <= 16) {
						fish_pos[i] = { n_r, n_c, 1 };
						fish_pos[map[n_r][n_c].num] = { r, c, 1 };

						map[r][c].dir = n_d;
						swap(map[r][c], map[n_r][n_c]);
						//swap_pos(fish_pos[i], fish_pos[map[n_r][n_c].num]);
						break;
					}

				}

			}
		}


	}
		


}

void copy_map(fish dst[4][4], fish src[4][4]) {
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			dst[i][j] = src[i][j];
		}
	} 
}

void copy_pos(pos dst[17], pos src[17]) {
	for (int i = 1; i <= 16; i++) {
		dst[i] = src[i];
	}
}


void dfs(int sum, int sh_row, int sh_col) {

	// first, move the fish
 	fish_move();

	// terminator
	// if nowhere else to go (shark), then return
	int n_r, n_c, n_d;
	fish t_fish, t_shark;
	fish backup[4][4];
	pos back_pos[17];

	n_d = map[sh_row][sh_col].dir;

	vector<int> leap; // how much leap that shark can take

	  
	for (int i = 1; i <= 3; i++) {
		n_r = sh_row + dR[n_d] * i;
		n_c = sh_col + dC[n_d] * i;

		if (isRange(n_r, n_c) && map[n_r][n_c].num != 0) {
			leap.push_back(i);
		}
	}

	// go home
	if (leap.empty()) {

		ans = max(ans, sum);
		return;

	}
	else {

		// move shark and dfs
		for (int i = 0; i < leap.size(); i++) {
			// new position
			n_r = sh_row + dR[n_d] * leap[i];
			n_c = sh_col + dC[n_d] * leap[i];

			// copy original
			t_shark = map[sh_row][sh_col];
			t_fish = map[n_r][n_c];
			copy_map(backup, map);
			copy_pos(back_pos, fish_pos);

			// move shark
			// empty original
			map[sh_row][sh_col].num = 0;


			// fill the new tile (obsorbs direction)
			map[n_r][n_c].num = 100;
			fish_pos[t_fish.num].alive = 0;


			// dfs
			dfs(sum + t_fish.num, n_r, n_c);


			// restore
			copy_map(map, backup);
			copy_pos(fish_pos, back_pos);
		}

	}

}


int main() {

	int t_n, t_d;
	fish start;
	ans = 0;

	for (int i = 0; i < 16; i++) {
		cin >> t_n >> t_d;
		map[i/4][i%4] = { t_n, t_d-1 };
		fish_pos[t_n] = {i/4, i%4, 1};
	}

	// shark eats the first one
	start = map[0][0];
	ans += start.num;

	map[0][0].num = 100;
	fish_pos[start.num].alive = 0;
	
	dfs(ans, 0, 0);

	cout << ans << endl;


}

 

 

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

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

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