인프런 커뮤니티 질문&답변

안녕하세요 ㅎㅎ

일단 제가 수정한 코드는 다음과 같습니다.

#include <bits/stdc++.h>

using namespace std; 
char v[1004][1004];
int fire[1004][1004];
int player[1004][1004];
bool visited[1004][1004];
deque<pair<int, int>> fire_q;
const int dr[] = { 0,1,0,-1 };
const int dc[] = { 1,0,-1,0 };
int main()
{ 
  memset(fire, -1, sizeof(fire));
  memset(player, -1, sizeof(player));
	
    int R, C, pr, pc;
	cin >> R >> C;
 
	string str;
	char ch;
	for (int r = 0; r < R; ++r)
	{
		cin >> str;
		for (int c = 0; c < C; ++c)
		{
			ch = str[c];
			v[r][c] = ch;
			if (ch == 'J')
			{
				pr = r, pc = c;
				player[r][c] = 0;
			}
			else if (ch == 'F')
			{
				fire_q.push_back({ r,c });
				fire[r][c] = 0;
			}
		}
	}
	
	while (!fire_q.empty())
	{
		//for (auto k : fire_q)
		//	cout << k.first << "," << k.second << " ";
		//print_2d_vector(fire);

		int r = fire_q.front().first;
		int c = fire_q.front().second;
		fire_q.pop_front();

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

			if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
			if (v[nr][nc] == '#' || fire[nr][nc] != -1) continue;

			fire_q.push_back({ nr,nc });
			fire[nr][nc] = fire[r][c] + 1;
		}

	}
    
    fire_q.push_back({pr, pc});
	while (!fire_q.empty())
	{
		//for (auto k : player_q)
		//cout << k.first << "," << k.second << " ";
		//print_2d_vector(player);

		int r = fire_q.front().first;
		int c = fire_q.front().second;
		fire_q.pop_front();

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

			if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
			if (v[nr][nc] == '#' || player[nr][nc] != -1) continue;

			fire_q.push_back({ nr,nc });
			player[nr][nc] = player[r][c] + 1;
		}

	}

	for (int r = 0; r < R; ++r)
	{
		for (int c = 0; c < C; ++c)
		{
			if (fire[r][c] == -1) continue;
			if (player[r][c] >= fire[r][c])
				player[r][c] = -1;
		}
	}
	//cout << "[Answer]";
	//print_2d_vector(player);

	fire_q.push_back({ pr, pc });
	while (!fire_q.empty())
	{
		//for (auto k : player_q)
		//	cout << k.first << "," << k.second << " ";
		//print_2d_vector(player);

		int r = fire_q.front().first;
		int c = fire_q.front().second;
		visited[r][c] = true;
		fire_q.pop_front();

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

			if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
			if (visited[nr][nc] == true || player[nr][nc] == -1) continue;

			fire_q.push_back({ nr,nc });
			player[nr][nc] = player[r][c] + 1;
		}
	}
	//cout << "[player]";
	//print_2d_vector(player);

	int min = 100000, tmp;
	for (int r = 0; r < R; ++r)
	{
		if (player[r][0] != -1)
		{
			if (min > player[r][0])
				min = player[r][0];
		}
		if (player[r][C - 1] != -1)
		{
			if (min > player[r][C - 1])
				min = player[r][C - 1];
		}
	}
	for (int c = 0; c < C; ++c)
	{
		if (player[0][c] != -1)
		{
			if (min > player[0][c])
				min = player[0][c];
		}
		if (player[R - 1][c] != -1)
		{
			if (min > player[R - 1][c])
				min = player[R - 1][c];
		}
	}
	if (min == 100000)
		cout << "IMPOSSIBLE\n";
	else
		cout << min + 1;

}

처음에는 지역변수로 선언된 것을 전역변수로 바꿔서 해결해보고자 했는데요.

전역변수가 더 메모리를 많이 쓸 수 있음. : 해당 부분은 교안에 나와있습니다. :)

이렇게 해도 메모리 초과가 뜹니다. 몇가지 반례도 넣어봤지만 괜찮습니다.

제 생각에는 불필요한 로직 때문에 그런 거 같습니다. 조금 효율적으로 바꿔보시면 되지 않을까 생각되는데요.

해당 로직은 다음과 같습니다.

1.

fire_q : queue로도 가능합니다.

2. 불필요한 로직

방문불가 맵전체순회 >> -1로 덮어쓰기 : player bfs 할 때 구할 수 있습니다.

visited = true하면서 player bfs : 방문배열에 최단거리를 넣어서 중복되는 로직을 제거해주세요.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

안녕하세요, 인프런 AI 인턴입니다. 메모리 초과와 관련된 문제에 대해 답변드릴게요.

먼저, 메모리 초과 문제는 보통 사용하는 자료구조(변수)가 많거나 큰 크기를 가지기 때문에 발생할 수 있습니다. 단순 계산으로 4MB가 초과되지 않는다고 해서 메모리 초과가 발생하지 않는 것은 아닙니다. 실제로는 여러 요인이 메모리 초과를 유발할 수 있습니다.

가능한 원인 중 하나는, 문제에서 제시한 알고리즘의 구현 방식입니다. 예를 들어, 벡터와 덱(deque)이 큰 크기를 가지거나 여러 번 사용된다면 메모리가 많이 소모될 수 있습니다. 또한, 반복문이나 재귀 함수의 사용으로 인해 메모리 사용량이 증가할 수도 있습니다.

또 다른 원인은 동적 할당으로 인한 메모리 누수입니다. 예를 들어, 동적으로 할당한 메모리를 해제하지 않고 반복적으로 사용하거나, 메모리를 할당한 후에 해제하지 않을 경우 메모리 누수가 발생할 수 있습니다. 따라서, 반복적으로 사용하는 경우에는 메모리를 할당한 후에 적절히 해제하는지 확인해보세요.

또한, 문제의 입력 데이터 크기에 따라 메모리 사용량도 달라질 수 있습니다. 예를 들어, 1000 * 1000 크기의 2차원 벡터는 4MB이지만, 입력 데이터의 크기에 따라 4MB를 여러 번 사용하게 되므로 메모리가 누적되어 초과될 수 있습니다.

해결 방법으로는 다음과 같은 접근 방식을 고려해볼 수 있습니다.
1. 필요한 변수와 자료구조의 크기를 최소화하기 위해 최적화된 알고리즘을 사용해보세요.
2. 동적 할당한 메모리를 적절히 해제하는지 확인해보세요.
3. 입력 데이터에 따라 크기가 늘어날 수 있는 자료구조에 대한 대안을 고려해보세요.
4. 문제를 해결하는 다른 알고리즘을 사용해보세요.

또한, Visual Studio에서 메모리 디버깅을 위해 “디버그” -> “윈도우” -> “기타 윈도우” -> “메모리” 메뉴를 통해 메모리 사용량을 확인할 수 있습니다. 문제가 발생하는 지점에서 메모리 사용량을 확인하고 비교해보세요.

그럼 메모리 초과 문제 해결에 도움이 되었으면 좋겠습니다. 추가로 궁금한 점이 있다면 언제든지 물어보세요. 좋은 결과를 기원합니다!