백준 16933 - 벽 부수고 이동하기 3(C++)

문제 링크입니다. https://www.acmicpc.net/problem/16933

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

BFS를 이용한 문제였습니다.

문제 조건

출력 예시

기존 벽 부수기 문제와는 다르게 밤과 낮 기능이 추가된 문제였습니다.
따라서 저는 구조체를 이용해 queue에 현재 좌표, 벽을 부순 횟수, 이동 횟수, 밤과 낮을 저장해줬습니다.

해당 좌표를 방문했는지를 확인하는 check배열은 2차원 배열로 선언하면 안됩니다.
벽을 1번 부수고 (X,Y)에 도달할 수도 있으며, 벽을 2번 부수고 (X,Y)에 도달할 수도 있습니다.
이는 모두 다른 경우이기에, 3차원 배열로 선언해주고, [X][Y][벽을 부순 횟수]로 해당 좌표를 저장해야합니다.

이동할 수 있는 방법은 5가지 입니다. (이동X + 상하좌우)
이동한 좌표에서 나올수 있는 경우는 4가지 입니다.
1. 낮이며, 해당 좌표가 벽이 아닌 경우, 이전에 방문하지 않았을 경우
-> 해당 좌표를 queue에 넣어주고, 낮을 밤으로 바꾸고, 이동 횟수를 하나 증가합니다.
2. 낮이며, 해당 좌표가 벽인 경우, 이전에 방문하지 않았을 경우
-> 해당 좌표를 queue에 넣어주고, 벽을 부순 횟수를 하나 증가, 낮을 밤으로 바꾸고 이동횟수를 하나 증가합니다.
3. 밤이며, 해당 좌표가 벽이 아닌 경우, 이전에 방문하지 않았을 경우
-> 해당 좌표를 queue에 넣어주고, 밤은 낮으로 바꾸고, 이동 횟수를 하나 증가합니다.
*4. 밤이며, 해당 좌표가 벽인 경우
-> 이동하기 전의 좌표를 queue에 넣어주고, 밤을 낮으로 바꾸고, 이동 횟수를 하나 증가합니다.

문제 접근 방법
1. 구조체를 이용해 queue에 좌표, 벽을 부순 횟수, 이동 횟수, 낮과 밤을 저장한다.
2. (1,1) 부터 시작하여, 5가지 방향을 확인한다.
3. 각 방향마다 4가지의 경우를 확인한다.
4. 탐색 도중, (N,M)에 도착할 경우 이동 횟수를 return 해준다.
5. 탐색을 마쳤는데도 도달하지 못했다면, -1를 return 해준다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int N, M, K;
int map[1001][1001];
int check[1001][1001][11];
int dx[5] = { 0,1,0,-1,0 };
int dy[5] = { 0,0,1,0,-1 };
typedef struct qu{
	int x;
	int y;
	int cnt;
	int times;
	int day; // 1 - 밤, 0 - 낮
}qu;

void input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			scanf("%01d", &map[i][j]);
		}
	}
}

int bfs() {
	queue<qu> q;
	check[1][1][0] = 1;
	q.push({ 1,1,0,1,0 });
	while (!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		int times = q.front().times;
		int day = q.front().day;
		q.pop();
		//cout << x << " " << y << " " << times << "\n";
		if (x == N && y == M) {
			return times;
		}
		for (int i = 0; i < 5; i++) {
			int xx = x + dx[i];
			int yy = y + dy[i];
			if (xx >= 1 && yy >= 1 && xx <= N && yy <= M) {
				if (day == 0) { // 낮
					if (map[xx][yy] == 0) {
						if (check[xx][yy][cnt] == 0) {
							check[xx][yy][cnt] = 1;
							q.push({ xx,yy,cnt, times+1,1 });
						}
					}
					else if (map[xx][yy] == 1) {
						if (cnt + 1 <= K && check[xx][yy][cnt + 1] == 0) {
							check[xx][yy][cnt + 1] = 1;
							q.push({ xx,yy,cnt + 1,times+1,1 });
						}
					}
				}
				else { // 밤
					if (map[xx][yy] == 0) {
						if (check[xx][yy][cnt] == 0) {
							check[xx][yy][cnt] = 1;
							q.push({ xx,yy,cnt,times+1,0 });
						}
					}
					else {
						q.push({ x,y,cnt,times+1,0 });
					}
				}
			}
		}
	}
	return -1;
}

void solve() {
	input();
	int ans = bfs();
	cout << ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	solve();
	return 0;
}

 

질문 및 조언 댓글 남겨주세요!