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

알고리즘 문제 전체 링크

 

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

 

 

BOJ 2206 : 벽 부수고 이동하기에서 벽을 K번 부술 수 있도록 코드를 수정하면 된다.

 

최대 10번까지 부술 수 있으므로 visit 배열을 10개 이상으로 만든다.

//int visit[2][MAX][MAX];
int visit[10 + 2][MAX][MAX];

 

BFS에서 out.k == 0인 경우를 out.k < K인 경우로 변경하고

visit[0]을 visit[out.k]로 visit[1]을 visit[out.k + 1]로 변경한다.

if (out.k < K) /* k < K일 때, */
{
	/* queue의 다음 좌표가 0이고 visit[out.k]도 0 */
	if (MAP[nr][nc] == 0 && visit[out.k][nr][nc] == 0)
	{
		queue[wp].r = nr;
		queue[wp].c = nc;
		queue[wp++].k = out.k;

		visit[out.k][nr][nc] = visit[out.k][out.r][out.c] + 1;
	}		
	/* queue의 다음 좌표가 1이고 visit[out.k + 1]도 0 */
	else if (MAP[nr][nc] == 1 && visit[out.k + 1][nr][nc] == 0)
	{
		queue[wp].r = nr;
		queue[wp].c = nc;
		queue[wp++].k = out.k + 1;

		visit[out.k + 1][nr][nc] = visit[out.k][out.r][out.c] + 1;
	}
}
else /* k = K일 때, */
{
	/* queue의 다음 좌표가 0이고 visit[out.k]도 0 */
	if (MAP[nr][nc] == 0 && visit[out.k][nr][nc] == 0)
	{
		queue[wp].r = nr;
		queue[wp].c = nc;
		queue[wp++].k = out.k;

		visit[out.k][nr][nc] = visit[out.k][out.r][out.c] + 1;
	}
}

 

최종 코드는 아래와 같다.

#include <stdio.h>

#define MAX (1000 + 10)

int N, M, K;
int MAP[MAX][MAX];
int visit[10 + 2][MAX][MAX];

typedef struct st
{
	int r;
	int c;
	int k;
}QUEUE;

QUEUE queue[MAX * MAX * 12]; 
int rp, wp;

void input()
{
	scanf("%d %d %d", &N, &M, &K);

	for (int r = 1; r <= N; r++)
		for (int c = 1; c <= M; c++)
			scanf("%1d", &MAP[r][c]);
}

void output(int map[][MAX])
{
	for (int r = 1; r <= N; r++)
	{
		for (int c = 1; c <= M; c++)
			printf("%d ", map[r][c]);
		putchar('\n');
	}
	putchar('\n');
}

/* 순서대로 왼쪽, 위, 오른쪽, 아래 */
int dr[] = { 0, -1, 0, 1 };
int dc[] = { -1, 0, 1, 0 };

int BFS(int s, int e)
{
	wp = rp = 0;

	visit[0][s][e] = 1;

	queue[wp].r = s;
	queue[wp++].c = e;

	while (wp > rp)
	{
		QUEUE out = queue[rp++];

		if (out.r == N && out.c == M) return visit[out.k][out.r][out.c];

		for (int i = 0; i < 4; i++)
		{
			int nr = out.r + dr[i];
			int nc = out.c + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;

			if (out.k < K) /* k < K일 때, */
			{
				/* queue의 다음 좌표가 0이고 visit[out.k]도 0 */
				if (MAP[nr][nc] == 0 && visit[out.k][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = out.k;

					visit[out.k][nr][nc] = visit[out.k][out.r][out.c] + 1;
				}		
				/* queue의 다음 좌표가 1이고 visit[out.k + 1]도 0 */
				else if (MAP[nr][nc] == 1 && visit[out.k + 1][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = out.k + 1;

					visit[out.k + 1][nr][nc] = visit[out.k][out.r][out.c] + 1;
				}
			}
			else /* k = K일 때, */
			{
				/* queue의 다음 좌표가 0이고 visit[out.k]도 0 */
				if (MAP[nr][nc] == 0 && visit[out.k][nr][nc] == 0)
				{
					queue[wp].r = nr;
					queue[wp].c = nc;
					queue[wp++].k = out.k;

					visit[out.k][nr][nc] = visit[out.k][out.r][out.c] + 1;
				}
			}
		}
	}

	return -1;
}

int main(void)
{
	input();

	printf("%d\n", BFS(1, 1));

	return 0;
}