ShaShaKa Dev Note

벽 부수고 이동하기

20 October 2019

문제 : https://www.acmicpc.net/problem/2206

이번은 "현재 상태"를 정점으로 표현하여 그래프를 만들고 최단거리를 구하는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int X, Y;

int head = 0;
int tail = 0;
int visit[1001][1001][2] = { 0 };
int **mat;
const int arr_size = 1000001;

int bfs();

struct Node
{
	int x, y, z, u;
	Node* myAlloc(int x, int y, int z, int u) {
		this->x = x;
		this->y = y;
		this->z = z;
		this->u = u;
		return this;
	}
}a[arr_size];

void add(int x, int y, int z, int u) {
	if (tail >= arr_size)
	{
		tail -= arr_size;
	}
	a[tail++].myAlloc(x, y, z, u);
}

Node* pull() {
	if (head == tail)
	{
		return NULL;
	}
	if (head >= arr_size)
	{
		head -= arr_size;
	}
	return &a[head++];
}


int main(void) {

	scanf("%d %d", &X, &Y);

	mat = new int*[X];
	for (int i = 0; i < X; i++)
	{
		mat[i] = new int[Y];
		for (int k = 0; k < Y; k++)
		{
			scanf("%1d", &mat[i][k]);
		}
	}

	add(0, 0, 0, 1);

	printf("%d", bfs());
}

void move(int x, int y, int z, int u) {
	if (x < 0 || y < 0 || x >= X || y >= Y)
	{
		return;
	}

	if (visit[x][y][z] != 0)
	{
		return;
	}

	if (mat[x][y] == 1)
	{
		if (z > 0) {
			return;
		}
		z = 1;
	}

	visit[x][y][z] = 1;

	add(x, y, z, u);

}

int bfs() {

	Node* node = pull();

	while (node != NULL)
	{

		if (node->x == X - 1 && node->y == Y - 1)
		{
			return node->u;
		}

		move(node->x - 1, node->y, node->z, node->u + 1);
		move(node->x + 1, node->y, node->z, node->u + 1);
		move(node->x, node->y - 1, node->z, node->u + 1);
		move(node->x, node->y + 1, node->z, node->u + 1);

		node = pull();
	}

	return -1;
}

먼저 Node를 선언하여, Circullar Queue를 생성하여 줍니다.
가장 먼저, 큐에 최초 시작하는 지점을 x,y, 현재 이동한 카운트, 즉 처음에는 0을 넣어줍니다.
해당 지점에서 사방으로 이동이 가능하므로, 상하좌우 지점을 체크해주도록 합니다.
해당 값이 1인 경우, 한번만 벽을 부술 수 있으므로 z를 1로 셋팅해주고, visit 항목도 해당 값이 0과 1인 경우로 두개로 체크해주도록 합니다.
해당 로직이 모두 수행된 이후까지 마지막 지점 값이 나오지 않으면 -1을 return해주도록 합니다.