14442 벽 부수고 이동하기 2

2206 벽 부수고 이동하기 문제의 심화 버전

벽을 여러번 부술 수 있을 때, 최단 경로 구하기

1. 문제

---

간단 설명

2206 문제와 마찬가지로

N과 M 의 행렬로 표현되는 맵이 제공 됨

1은 벽, 0은 통과할 수 있는곳

(1,1)에서 (N,M)의 좌표로 이동하는데 최단 경로 구하기

그런데 K번 벽을 부술 수 있음

벽을 부수고 이동하는게 더 빠르다면, 벽을 부수고 이동한다

2. 문제 분석

---

필요변수

N, M 그리고 맵 map[N][M]

K번 부술 수 있음

K번 뿌술 수 있으므로 방문 체크 배열 visited[N][M][K].

그 외 BFS에 필요한 재료들 Node 구조체, direct[4][2] 등

주의점

• 맵 정보가 문자열로 주어짐. 이를 쪼개서 저장
• 기존 BFS처럼 visited[dy][dx] == 1이라고 무조건 continue 하면 시간초과
  • 맵이 0이면, visited[dy][dx][now.w]를 체크하고
  • 맵이 1이면, 벽 부술수 있는 개수를 보고 visited[dy][dx][now.w+1]를 체크해야함

알고리즘

1. 입력받기
2. BFS 시작. 큐에 시작지점 넣기
3. 큐가 빌때까지 다음을 반복
    3-1. 큐의 맨 앞을 꺼내 도착지점인지 확인
    3-2. 아니라면 4방향 탐색 시작
        3-2-1. 경계 밖이라면 패스
        3-2-2. 다음 방문할곳이 통과 가능한 곳이고, 방문 기록이 없다면
            - 큐에 넣고 방문처리 배열에 현재 값 + 1 을 기록함
        3-2-3. 다음 방문할곳이 통과 불가능한 곳이라면, 
            - 벽 부술 수 있는 기회가 남아있는지, visited[dy][dx][now.w]가 비어있는지 확인
            - 둘다 OK라면 큐에 now + 1로 수정해서 넣고, visited[dy][dx][now.w + 1]에 현재 visted값 +1을 저장한다

3. 소스코드

---

#include <iostream>
#include <queue>

using namespace std;

#define MAX 1001

int N, M, K;
int map[MAX][MAX];
int visited[MAX][MAX][11];

struct Node {
	int y;
	int x;
	int w;
};

int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

// 디버그용 출력 함수. 현재 벽 부순 개수를 받아 visited 배열을 출력함
void debug_print(int w) {
	printf("===================================\n부신 벽 개수 : %d\n", w);
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			printf("%d ", visited[y][x][w]);
		}
		printf("\n");
	}
}


int BFS() {
	queue<Node> qu;
	qu.push({ 0,0,0 });
	visited[0][0][0] = 1;

	while (!qu.empty()) {
		Node now = qu.front();
		qu.pop();

		// debug_print(now.w);

		// 목적지라면 최단거리를 출력
		if (now.y == N - 1 && now.x == M - 1) {
			return visited[now.y][now.x][now.w];
		}
	
		// 4방향 탐색 시작
		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + now.y;
			int dx = direct[t][1] + now.x;

			// 경계 처리 : 맵 밖으로 벗어나면 패스
			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue;
			
			// 다음 칸이 이동가능하고, 방문한 기록이 없는 곳일 때
			// 기존 BFS처럼 처리
			if (map[dy][dx] == 0 && visited[dy][dx][now.w] == 0) {
				visited[dy][dx][now.w] = visited[now.y][now.x][now.w] + 1;
				qu.push({ dy, dx, now.w });
			}
			// 다음칸이 이동 불가능하고, 벽 부술 기회가 남아있고, 
			// 방문한 기록이 없는 곳일 때 (now.w 가 아닌 now.w + 1 에 주의)
			else if (map[dy][dx] == 1 && now.w < K && visited[dy][dx][now.w + 1] == 0) {
				visited[dy][dx][now.w + 1] = visited[now.y][now.x][now.w] + 1; // 벽을 부숨
				qu.push({ dy, dx, now.w + 1 });
			}
		}
	}

	return -1;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	freopen_s(new FILE*, "input.txt", "r", stdin);

	cin >> N >> M >> K;
	// 문자열을 입력받아 문자로 나눠 맵에 넣음
	for (int y = 0; y < N; y++) {
		string tmp; cin >> tmp;
		for (int x = 0; x < tmp.size(); x++) {
			map[y][x] = tmp[x] - '0';
		}
	}

	// BFS 시작
	int ret = BFS();

	cout << ret;

	return 0;
}

이제 벽을 여러개 부술 수 있는 힘을 얻었다