백준 16933 c++ "벽 부수고 이동하기 3" -[PlusUltraCode]

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

16933번: 벽 부수고 이동하기 3

 

[필자 사고]

이 문제는 너비우선 탐색을 이용한 BFS탐색 문제이다.

 

벽 부수고 이동하기1,2를 풀어 봤을 것이다. 벽 부수고 시리즈의 공통점은

 

1이라는 해당 장애물이 있어 능력을 이용해 이 벽을 부술지 말지 결정하는거다.

 

다른 문제와 다르게 이 문제만의 특이한 점은 밤과 낮에 행동하는 방식이 다르다는 점이다.

 

필자는 처음에 밤과 낮에 따라 방문되는 지점이 다른거라 생각해 visted[낮,밤][능력][세로][가로] 총 4차원 배열을 선언하여

문제를 푼 결과 시간초과가 되었다.

 

잠시 머리를 식히고 생각해보니 굳이 낮,밤을 visted에 저장안해도 되었다. 

 

//벽일때

  //낮일때

    //능력사용

  //밤일때

    //기다린다

 

//벽이 아닐때

  //이동한다.

 

 

위와 같은 형식으로 조건문을 완성하면 된다.

 

여기서 주의할 점은 다른 조건문들은 방문하지 않은 새삥이라 방문처리 true를 해줘야 되지만

 

밤일때 기다린다에서 움직이지 않고 해당 구역을 대기하는 거라 방문처리 visted를 하면 원하는 결과를 얻지 못하게된다

 

이 부분만 조심하면 문제를 해결할 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <tuple>

using namespace std;

int N, M, K;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };

typedef struct Node {
	int sero;
	int garo;
	int count;
	int crush;
	int time;
}Node;

vector<vector<int>> Arr;
bool visited[11][1001][1001];

bool Inside(int sero, int garo) {
	if (sero >= 0 && sero < N && garo >= 0 && garo < M)return true;
	return false;
}

void Input() {
	cin >> N >> M >> K;
	Arr.resize(N);
	for (int i = 0; i < N; i++) {
		Arr[i].resize(M);
	}
	string str;
	for (int i = 0; i < N; i++) {
		cin >> str;
		for (int k = 0; k < str.size(); k++) {
			Arr[i][k] = str[k] - '0';
		}
	}
}
//sero garo count crush time
void BFS() {
	queue<Node>myQueue;
	myQueue.push({ 0,0,1,K,0 });
	visited[K][0][0] = true;
	while (!myQueue.empty()) {
		int nowSero = myQueue.front().sero;
		int nowGaro = myQueue.front().garo;
		int acCount = myQueue.front().count;
		int nowCrush = myQueue.front().crush;
		int nowTime = myQueue.front().time;


		if (nowSero == N - 1 && nowGaro == M - 1) {
			cout << acCount;
			return;
		}
		myQueue.pop();
		for (int i = 0; i < 4; i++) {
			int nextSero = nowSero + dy[i];
			int nextGaro = nowGaro + dx[i];
			int nextTime = (nowTime + 1) % 2;
			if (Inside(nextSero, nextGaro) == false)continue;
			//낮일 때
				//벽을 만나 능력사용
				//능력사용 안하고 그냥 가기

			//밤일 때
				//벽을 만나 제자리 대기
				//능력사용 안하고 그냥가기
			if (Arr[nextSero][nextGaro] == 0) {
				if (visited[nowCrush][nextSero][nextGaro] == false) {
					visited[nowCrush][nextSero][nextGaro] = true;
					myQueue.push({ nextSero,nextGaro,acCount + 1,nowCrush,nextTime });
					
				}
			}
			else if (Arr[nextSero][nextGaro] == 1) {
				//능력이 있어야만 통과 없으면 어처피 낮이 되도 못 부슴
				//낮일 경우 벽을 부수기
				//밤일 경우 대기
				if (nowCrush > 0) {
					if (nowTime == 0) {
						if (visited[nowCrush - 1][nextSero][nextGaro] == false) {
							visited[nowCrush - 1][nextSero][nextGaro] = true;
							myQueue.push({ nextSero,nextGaro,acCount + 1,nowCrush-1,nextTime });
						}
					}
					else {	
							myQueue.push({ nowSero,nowGaro,acCount + 1,nowCrush ,nextTime });	
					}
				}

			}
		}
	}
	cout << -1;
	return;
}

int main(void) {
	Input();
	BFS();
}