관리 메뉴

KoreanFoodie's Study

SW 역량테스트 - [백준] 새로운 게임 2 문제 풀이/해답/코드 (C++ / JAVA) 본문

Data Structures, Algorithm/SW 역량테스트

SW 역량테스트 - [백준] 새로운 게임 2 문제 풀이/해답/코드 (C++ / JAVA)

hashnut 2020. 10. 15. 23:53


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

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

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

 


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

해답 코드 : 

 

#include <iostream>
#include <deque>

using namespace std;

typedef struct chess{

	int num;
	int row;
	int col;
	int dir;

}chess;

int N, K;
int color[12][12];

deque<chess> map[12][12];
chess chess_pos[10];

int ans;
bool flag;

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

// return opposite direction
int op_dir(int d) {
	if (d == 0) return 1;
	else if (d == 1) return 0;
	else if (d == 2) return 3;
	else return 2;
}


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

// if there are more than 4 chess in a single tile, flag = true;
void move_red(chess cur_ch, int n_r, int n_c) {

	// queue for chesses above 'cur_ch'
	deque<chess> chQ;
	int c_r, c_c;

	c_r = cur_ch.row;
	c_c = cur_ch.col;
	// check is there any chess "on" the 'cur_ch'
	for (int i = map[c_r][c_c].size() - 1; i >= 0; i--) {
		chQ.push_back(map[c_r][c_c][i]);
		if (map[c_r][c_c][i].num == cur_ch.num) {
			break;
		}
	}

	// delete chess
	for (int i = 0; i < chQ.size(); i++) {
		map[c_r][c_c].pop_back();
	}

	// add chess
	for (int i = 0; i < chQ.size(); i++) {
		map[n_r][n_c].push_back(chQ[i]);
	}

	// update chess_pos
	for (int i = 0; i < chQ.size(); i++) {
		chess_pos[chQ[i].num].row = n_r;
		chess_pos[chQ[i].num].col = n_c;
	}

	if (map[n_r][n_c].size() >= 4) {
		flag = true;
	}
}

// if there are more than 4 chess in a single tile, flag = true;
void move_white(chess cur_ch, int n_r, int n_c) {

	// queue for chesses above 'cur_ch'
	deque<chess> chQ;
	int c_r, c_c;

	c_r = cur_ch.row;
	c_c = cur_ch.col;
	// check is there any chess "on" the 'cur_ch'
	for (int i = map[c_r][c_c].size()-1; i >= 0; i--) {
		chQ.push_front(map[c_r][c_c][i]);
		if (map[c_r][c_c][i].num == cur_ch.num) {
			break;
		}
	}

	// delete chess
	for (int i = 0; i < chQ.size(); i++) {
		map[c_r][c_c].pop_back();
	}

	// add chess
	for (int i = 0; i < chQ.size(); i++) {
		map[n_r][n_c].push_back(chQ[i]);
	}

	// update chess_pos
	for (int i = 0; i < chQ.size(); i++) {
		chess_pos[chQ[i].num].row = n_r;
		chess_pos[chQ[i].num].col = n_c;
	}

	if (map[n_r][n_c].size() >= 4) {
		flag = true;
	}
}


// if there are more than 4 chess in a single tile, flag = true;
void move() {
	
	int c_num, c_r, c_c;
	int n_r, n_c;
	chess t_chess;

	for (int ch = 0; ch < K; ch++) {

		t_chess = chess_pos[ch];
		c_num = t_chess.num;
		c_r = t_chess.row;
		c_c = t_chess.col;
		n_r = t_chess.row + dR[t_chess.dir];
		n_c = t_chess.col + dC[t_chess.dir];
		
		// case 2 : blue (for range check)
		if (!isRange(n_r, n_c) || color[n_r][n_c] == 2) {

			n_r += dR[op_dir(t_chess.dir)] * 2;
			n_c += dC[op_dir(t_chess.dir)] * 2;
			
			// direction change
			t_chess.dir = op_dir(t_chess.dir);
			chess_pos[ch].dir = t_chess.dir;

			// Out of range or Blue again
			if (!isRange(n_r, n_c) || color[n_r][n_c] == 2) {
				// do nothing, just update the direction
				for (int i = 0; i < map[c_r][c_c].size(); i++) {
					if (map[c_r][c_c][i].num == c_num) {
						map[c_r][c_c][i].dir = t_chess.dir;
					}
				}

			}
			else if (color[n_r][n_c] == 0) {
				move_white(t_chess, n_r, n_c);
			}
			else {
				move_red(t_chess, n_r, n_c);
			}

		}
		
		// case 0 : white
	
		else if (color[n_r][n_c] == 0) {

			move_white(t_chess, n_r, n_c);

		}

		// case 1 : red

		else {

			move_red(t_chess, n_r, n_c);

		}

	}

}



int main() {

	cin >> N >> K;

	int t_r, t_c, t_d;
	int chess_num = 0;
	int time;
	flag = false;

	chess t_chess;

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

		for (int j = 0; j < N; j++) {
			cin >> color[i][j];
		}
	
	}

	for (int i = 0; i < K; i++) {
		cin >> t_r >> t_c >> t_d;
		t_chess = {i, t_r - 1, t_c - 1, t_d - 1};
		chess_pos[i] = t_chess;
		map[t_r - 1][t_c - 1].push_back(t_chess);
	}

	for (time = 1; time <= 1000; time++) {
		move();
		if (flag) {
			break;
		}
	}

	if (time > 1000) {
		cout << -1 << endl;
	}
	else {
		cout << time << endl;
	}



}

 

 

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

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

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

 
0 Comments
댓글쓰기 폼