[풀이, 디버깅필요]백준 및 SW 아카데미 풀이(III/16954)

문제풀이

움직이는 미로 탈출(16954, BFS)

• 벽은 1초에 한 칸씩 아래로 내려온다. (까다로운 조건)
• 크기 8X8 체스판에서 가장 왼쪽 아래칸에서 가장 오른쪽 위칸으로 이동 가능한지?
• 벽의 크기가 8X8이므로 8초동안의 벽을 모두 기록한다.

BFS에서는 할 수 있는게 같아야 같은 정점이다. (강의자료 택시, 버스 참고)

• 따라서 칸의 정보(r,c,t)로 시간에 대한 정보도 필요하다.

꽤 많이 날렸네…

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;



int dx[] = {1, 1, 0, -1,-1, -1, 0, 1};
int dy[] = {0, 1, 1,  1, 0, -1,-1,-1};
bool converted_map[8][8];
bool check_map[8][8];
int rock_cnt=0;
bool Answer;

void rock_count() {
	rock_cnt=0;
	for(int i=0; i<8; i++){
		for(int j=0; j<8; j++){
			if(converted_map[i][j]) rock_cnt++;
		}
	}
}

void move_wall(){
	for(int i=0; i<8; i++){
		for(int j=0; j<8; j++){
			if(converted_map[i][j]){
				converted_map[i][j]=false;
				if(j!=0) converted_map[i][j-1]=true;
			}
		}
	}
}

void bfs(int rs, int cs){

	check_map[rs][cs]=true;

	queue<pair <int, int>> q;
	q.push(make_pair(rs,cs));

	while(!q.empty()){

		pair<int, int> x = q.front(); q.pop();
		for(int k=0; k<8; k++){

			//정답1. 바위가 없는 경우 (무조건 갈 수 있음)
			rock_count();
			if(rock_cnt == 0) {
				Answer = true;
				return;
			}

			//정답2. 가장 윗 칸으로 올라간 경우 (무조건 갈 수 있음)
			if(x.first == 7)
			{
				Answer = true;
				break;
			}

			pair<int, int> y = make_pair(x.first + dx[k], x.second+ dy[k]);
			//체스판 범위 내에서
			if(y.first>=0  && y.first<8 && y.second>=0 && y.second<8)
			{
				//이동할 수 있는 칸이면 (0=빈칸, 1은 벽)
				if(!converted_map[y.first][y.second])
				{
					//이동 후 벽이동
					q.push(y);
					move_wall();

				}

			}
		}
	}
}


int main(){

	char map[8][8];
	int rs=0, cs=0;

	//입력 완료
	for(int i=0; i<8; i++){
		for(int j=0; j<8; j++){
			cin >> map[i][j];
		}
	}

	//변환 완료
	for(int i=0; i<8; i++){
		for(int j=0; j<8; j++){
			if(map[i][j]=='.') converted_map[i][j] = false;
			else {
				converted_map[i][j] = true;
			}
		}
	}

	bfs(rs, cs);

	cout << Answer;
}

보물상자 비밀번호

• 갑자기 백준에서 소스제출이 안되어서 다른 문제를 풀러 잠시 돌아옴 ㅠ,,,
• 각 변에 16진수 숫자(0~F)가 적혀있는 보물상자가 있다.
• 뚜껑은 시계방향으로 돌릴 수 있고 한 번 돌릴 때마다 숫자가 한 칸씩 회전한다
• 각 변에는 동일한 개수의 숫자가 있고 시계방향 순으로 높은자리 숫자에 해당하며 하나의 수를 나타낸다.
• 자물쇠의 비밀번호는 보물상자에 적힌 숫자로 만들 수 있는 모든 수 중 K번쨰로 큰 수를 10진수로 변환한 수이다.
• N은 4의배수이며 8이상 28이하이다.

꿀TIP: 같은 숫자를 세지 않도록 주의한다.

N=4일 때는 1회전 시 원상복구, 1개 단위 묶음 N=8일 때는 2회전 시 원상복구, 2개 단위 묶음 N=12일 때는 3회전 시 원상복구, 3개 단위 묶음 N=(4*B)일 때는 B회전 시 원상복구, B개 단위 묶음

따라서

1. 숫자 전체를 큐에넣는다
2. 묶음단위 진법 변환 한다.
3. 중복이 없으면 벡터에 집어넣고 소팅한다.

1~3을 B-1회 반복한다

미완성코드 디버깅필요

#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int convertDex(char bucket[]){
	int decimal = 0;
	int position =0;
	int maxidx = strlen(bucket)-1;

	for(int i= maxidx; i>=0; i--){
		char ch = bucket[i];
		 if (ch >= 48 && ch <= 57)         // 문자가 0~9이면(ASCII 코드 48~57)
		{
			decimal += (ch - 48) * pow(16, position);
		}
		else if (ch >= 65 && ch <= 70)    // 문자가 A~F이면(ASCII 코드 65~70)
		{
			decimal += (ch - (65 - 10)) * pow(16, position);
		}
		else if (ch >= 97 && ch <= 102)
		{
			decimal += (ch - (97 - 10)) * pow(16, position);
		}
		position++;
	}
	return decimal;
}

int main(int argc, char** argv)
{
	int test_case;
	int T,B;
	char num[30];

	vector<int> numBucket;
	vector<char> qvec;
	queue<char> q;


	cin>>T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		/////////////////////////////////////////////////////////////////////////////////////////////
		int n, k;
		int count=0;
		char temp[4];

		cin >> n >> k;

		for(int i=0; i<n; i++){
			cin >> num[i];
		}

		B = (n/4);

		//B번만큼 로테이션 및 반복작업
		while(B){
			//1. 숫자 전체를 큐에 넣는다.
			for(int i=0; i<n; i++){
				q.push(num[i]);
				qvec.push_back(num[i]);
			}

			//2. 묶음 단위 진법 변환한다.(4*B = N = B개 단위로 묶음)
			for(int i=0; i<4; i++){

				//B가 줄어들어서 값이 이상해졌다!
				//1묶음 = n/4개
				for(int j=1; j<=n/4; j++){
					//첫 번째 꺼
					temp[j-1] = qvec[count];
					//cout << "count =" << count << endl;
					//cout << "temp["<<count<<"] =" << qvec[count]<<"\n";
					count++;
				}
				//2-1 진법변환 완료 후 중복되지 않았다면 숫자는 벡터에 집어넣는다
				if(find(numBucket.begin(), numBucket.end(), convertDex(temp))!= numBucket.end())
				{
					numBucket.push_back(convertDex(temp));
				}
				cout << "convertDex(" << temp << ")= " << convertDex(temp)<<endl;
			}
//			//2-2 로테이션 및 초기화
//			for(int i=0; i<qvec.size(); i++){
//				cout << "qvec["<< i<< "]=" <<qvec[i]<<endl;
//			}


			char last = qvec[0];
			qvec.erase(qvec.begin());
			qvec.push_back(last);
			count = 0;
			B--;
		}

		//sort(numBucket.begin(), numBucket.end());
//		int Answer = numBucket[k];
//		cout << "#" << test_case << " "<< Answer << "\n";

	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}