글 읽기 - 무슨 차이일까요???

baj2121 3년 전 0

방향에 대해서 구조체 배열을 쓰지 않고 풀어서 작성한 경우 메모리 초과가 나오는데

똑같은로직에 그냥 방향만 구조체 배열로 for문 반복해서 진행하면 정답으로 뜨거든요...

도대체 무슨 차이가 있는거죠???

#include<iostream>
#include<queue>
using namespace std;

int K, W, H;
int arr[200][200];
bool visit[30][200][200];

struct Node {
	int y;
	int x;
	int cur;
	int k;
};

int main(void)
{
	cin >> K >> W >> H;
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> arr[i][j];
		}
	}

	queue<Node> que;
	que.push({ 0,0,0,0});
	
	while (!que.empty())
	{
		int y = que.front().y;
		int x = que.front().x;
		int cur = que.front().cur;
		int k = que.front().k;
		que.pop();


		if (y == H - 1 && x == W - 1)
		{
			cout << cur << endl;
			return 0;
		}

		if (y - 1 >= 0 && x - 2 >= 0 && k < K)
		{
			if (!visit[k][y - 1][x - 2] && !arr[y - 1][x - 2])
			{
				visit[k + 1][y - 1][x - 2] = true;
				que.push({ y - 1,x - 2,cur + 1,k + 1 });
			}
		}

		if (y - 2 >= 0 && x - 1 >= 0 && k < K)
		{
			if (!visit[k][y - 2][x - 1] && !arr[y - 2][x - 1])
			{
				visit[k + 1][y - 2][x - 1] = true;
				que.push({ y - 2, x - 1, cur + 1,k + 1 });
			}
		}

		if (y - 2 >= 0 && x + 1 < W && k < K)
		{
			if (!visit[k][y - 2][x + 1] && !arr[y - 2][x + 1])
			{
				visit[k + 1][y - 2][x + 1] = true;
				que.push({ y - 2, x + 1, cur + 1,k + 1 });
			}
		}

		if (y - 1 >= 0 && x + 2 < W && k < K)
		{
			if (!visit[k][y - 1][x + 2] && !arr[y - 1][x + 2])
			{
				visit[k + 1][y - 1][x + 2] = true;
				que.push({ y - 1, x + 2, cur + 1,k + 1 });
			}
		}

		if (y + 1 < H && x - 2 >= 0 && k < K)
		{
			if (!visit[k][y + 1][x - 2] && !arr[y + 1][x - 2])
			{
				visit[k + 1][y + 1][x - 2] = true;
				que.push({ y + 1, x - 2, cur + 1,k + 1 });
			}
		}

		if (y + 2 < H && x - 1 >= 0 && k < K)
		{
			if (!visit[k][y + 2][x - 1] && !arr[y + 2][x - 1])
			{
				visit[k + 1][y + 2][x - 1] = true;
				que.push({ y + 2, x - 1, cur + 1,k + 1 });
			}
		}

		if (y + 2 < H && x + 1 < W && k < K)
		{
			if (!visit[k][y + 2][x + 1] && !arr[y + 2][x + 1])
			{
				visit[k + 1][y + 2][x + 1] = true;
				que.push({ y + 2, x + 1, cur + 1,k + 1 });
			}
		}

		if (y + 1 < H && x + 2 < W && k < K)
		{
			if (!visit[k][y + 1][x + 2] && !arr[y + 1][x + 2])
			{
				visit[k + 1][y + 1][x + 2] = true;
				que.push({ y + 1, x + 2, cur + 1,k + 1 });
			}
		}


		if (y - 1 >= 0)
		{
			if (!visit[k][y - 1][x] && !arr[y - 1][x])
			{
				visit[k][y - 1][x] = true;
				que.push({ y - 1, x, cur + 1,k });
			}
		}

		if (y + 1 < H)
		{
			if (!visit[k][y + 1][x] && !arr[y + 1][x])
			{
				visit[k][y + 1][x] = true;
				que.push({ y + 1, x, cur + 1,k });
			}
		}

		if (x - 1 >= 0)
		{
			if (!visit[k][y][x - 1] && !arr[y][x - 1])
			{
				visit[k][y][x - 1] = true;
				que.push({ y, x - 1, cur + 1,k });
			}
		}

		if (x + 1 < W)
		{
			if (!visit[k][y][x + 1] && !arr[y][x + 1])
			{
				visit[k][y][x + 1] = true;
				que.push({ y, x + 1, cur + 1,k });
			}
		}
	}


	cout << -1 << endl;
	return 0;
	
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

무슨 차이일까요???

baj2121 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말