[Algorithm][C++] BOJ 14442 벽 부수고 이동하기 2

url: https://www.acmicpc.net/problem/14442

14442번: 벽 부수고 이동하기 2

 

풀이 핵심

1. bool type의 방문 여부 확인 용 3차원 배열

2. queue 최대 크기 (1000 * 1000 * 10)

3. 다음 탐색 위치가 벽이면서 현재 벽을 부순 횟수가 K보다 작다면 다음과 같이 큐에 추가

if (map[nr][nc]) {
  if (cur.wall < K) {
    visited[nr][nc][cur.wall] = visited[nr][nc][cur.wall + 1] = true;
    push(nr, nc, cur.wall + 1, cur.dist + 1);
  }
}

 

코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAXN (1000)

int R, C, K;
int map[MAXN + 1][MAXN + 1];
bool visited[MAXN + 1][MAXN + 1][10 + 1];

struct INFO {
	int r, c, wall, dist;
};

INFO q[MAXN * MAXN * 10];
int fr, re;
void push(int r, int c, int wall, int dist) {
	q[re].r = r, q[re].c = c;
	q[re].wall = wall;
	q[re++].dist = dist;
}
INFO front() { return q[fr]; }
void pop() { fr++; }
int isEmpty() {
	if (fr == re) return 1;
	return 0;
}

int BFS() {
	push(1, 1, 0, 1);
	visited[1][1][0] = true;
	while (!isEmpty()) {
		INFO cur = front();
		pop();
		if (cur.r == R && cur.c == C) {
			return cur.dist;
		}
		const int dr[] = { 1,-1,0,0 };
		const int dc[] = { 0,0,1,-1 };
		for (int dir = 0; dir < 4; dir++) {
			int nr = cur.r + dr[dir];
			int nc = cur.c + dc[dir];
			if (nr < 1 || nr > R || nc < 1 || nc > C) continue;
			if (visited[nr][nc][cur.wall]) continue;
			if (map[nr][nc]) {
				if (cur.wall < K) {
					visited[nr][nc][cur.wall] = visited[nr][nc][cur.wall + 1] = true;
					push(nr, nc, cur.wall + 1, cur.dist + 1);
				}
			}
			else {
				visited[nr][nc][cur.wall] = true;
				push(nr, nc, cur.wall, cur.dist + 1);
			}
		}
	}
	return -1;
}

int main() {
	scanf("%d %d %d", &R, &C, &K);
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			scanf("%1d", &map[i][j]);
		}
	}
	printf("%d", BFS());
	return 0;
}

 

아쉬운 점

메모리 크기가 너무 크므로 원형 큐 또는 STL을 사용했어야 했다.

STL 사용 법을 익혀야겠다.