[BOJ] 14442번 벽 부수고 이동하기2(C++)

풀이 소요시간 : 25분

난이도에 비해 풀이 소요시간이 적은 이유는 얼마전 비슷한 문제를 풀어보았기 때문이다.
여러개의 이동 타입이 존재함에 따라 방문배열을 조정하는 접근방식을 사용한다면, 문제 자체는 별다른 구현력을 요구하지 않기때문에 빠르게 풀 수 있었다.

그나마 골드 난이도의 문제를 나름 풀어낼 수 있는 유형은 탐색뿐이다. 그리디 & 구현 유형의 문제는 실버 상위 난이도만 되어도 골머리를 앓는 경우가 허다하다. 방금 전에도 실버난이도의 구현문제를 스스로 힘으로 풀지못하고 탐색문제로 도망쳐온 것이다. 앞으로는 탐색문제는 가끔 풀고 구현, DP, 그리디 문제를 보완하는데 많은 시간을 투자해야겠다.

전체 코드

#include<iostream>
#include<string>
#include<queue>
using namespace std;

int N, M, K;
int Map[1001][1001];
int Visit[1001][1001][11];

struct Position {
	int x;
	int y;
	int time;
	int crash; 
};
queue<Position> Q;


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


void Input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); j++) {
			Map[i][j + 1] = str[j] - '0';
		}
	}
	Q.push({ 1, 1, 0, 0 });
	Visit[1][1][0] = 1;
}


void Bfs() {

	while (!Q.empty()) {

		int px = Q.front().x;
		int py = Q.front().y;
		int time = Q.front().time;
		int crash = Q.front().crash;
		Q.pop();

		if (px == N && py == M) {
			cout << time + 1 << '\n';
			return;
		}

		for (int i = 0; i < 4; i++) {
			int nx = px + dx[i];
			int ny = py + dy[i];

			if (nx < 1 || ny < 1 || nx > N || ny > M) continue;

			if (crash == K) {

				if (Map[nx][ny] == 1) continue;
				if (Visit[nx][ny][crash] == 1) continue;

				Visit[nx][ny][crash] = 1;
				Q.push({ nx, ny, time + 1, crash });

			}
			else { 

				if (Map[nx][ny] == 1) {
					if (Visit[nx][ny][crash + 1] == 0) {
						Visit[nx][ny][crash + 1] = 1;
						Q.push({ nx, ny, time + 1, crash + 1 });
					}
				}
				else {
					if (Visit[nx][ny][crash] == 0) {
						Visit[nx][ny][crash] = 1;
						Q.push({ nx, ny, time + 1, crash });
					}
				}

			}

		}


	}

	cout << -1 << '\n';

}


int main() {
	Input();
	Bfs();
}