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

안녕하세요 우진님 ㅎㅎ

보통은 이렇게 모듈화를 했다고 시간초과가 나진 않지만 이문제가 조금은 시간초과가 타이트한 것 같습니다.

그러나 제가 한번 시간초과가 안나게끔 만들어봤는데요. 모듈화 + 함수에 인자를 넘길 때 call by reference로 넘기게 되면 조금은 빨라집니다.

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, -1, 0, 1 };

bool CheckPos(int x, int y, int n, vector<vector<int>>& visited)
{
	if (y < 0 || y >= n || x < 0 || x >= n) return false;
	if (visited[y][x]) return false;

	return true;
}

bool CheckCity(int l, int r, int a, int b)
{
	int c = abs(a - b);
	if (c >= l && c <= r)
		return true;
	return false;
}

int dfs(vector<vector<int>>& vec, vector<vector<int>>& visited, vector<pair<int, int>>& citys, int n, int l, int r, int y, int x)
{
	int sum = vec[y][x];
	for (int i = 0; i < 4; ++i)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (CheckPos(nx, ny, n, visited) && CheckCity(l, r, vec[y][x], vec[ny][nx]))
		{
			visited[ny][nx] = 1;
			citys.push_back({ ny, nx });
			sum += dfs(vec, visited, citys, n, l, r, ny, nx);
		}
	}

	return sum;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
    cout.tie(NULL);
	int n, r, l, ret = 0;
	
	cin >> n >> l >> r;

	vector<vector<int>> vec(n, vector<int>(n, 0));
	vector<vector<int>> visited(n, vector<int>(n, 0));
	vector<pair<int, int>> citys;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			cin >> vec[i][j];
		}
	}

	while (true)
	{
        fill(visited.begin(), visited.end(), vector<int>(n, 0));
		bool flag = false;
		for (int i = 0; i < n; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (visited[i][j] == 0)
				{
					citys.clear();
					citys.push_back({ i, j });
					visited[i][j] = 1;
					int sum = dfs(vec, visited, citys, n, l, r, i, j);
					if (citys.size() == 1) continue;
					
					for (pair<int, int> &p : citys)
					{
						vec[p.first][p.second] = sum / (int)citys.size();
					}
					flag = true;
				}
			}
		}
		if (flag == false)
			break;
		ret++;
	}

	cout << ret << '\n';

	return 0;
}

참고부탁드립니다.

앞으로도 이렇게 모듈화 해도 괜찮습니다. 잘 짜셨어요 ㅎㅎ

감사합니다.

안녕하세요 우진님 ㅎㅎ

맞은 코드도 부탁드립니다.

안녕하세요, 인프런 AI 인턴입니다. 최우진님.

시간 초과 문제는 알고리즘의 효율성과 직접적으로 관련이 있습니다. 일반적으로 함수 호출은 약간의 오버헤드를 발생시키기 때문에, 특히 재귀적으로 많이 호출되는 함수의 경우 그 오버헤드가 누적될 수 있습니다. DFS(깊이 우선 탐색)와 같은 알고리즘에서는 이러한 함수 호출 오버헤드가 문제가 될 수 있습니다.

DFS 등 재귀가 많은 알고리즘의 경우, 여러 작은 함수를 호출하는 것보다 주요 로직을 하나의 함수에 모아서 구현하는 것이 시간 절약에 도움이 될 수 있습니다. 이는 함수 호출 시 스택에 저장되는 정보 등을 줄이는 데 유리합니다. 하지만 이와 같은 최적화는 코드의 가독성을 떨어뜨릴 수 있으므로, 코드를 단순하고 이해하기 쉬운 방식으로 유지하는 것이 중요합니다. 현업에서는 코드의 유지보수성도 중요한 요소이므로, 알고리즘의 복잡도를 최소화하는 것이 더 중요합니다.

관련된 유사 질문과 답변을 링크해드리니 참고해 주시기 바랍니다:

• “시간초과 문의”: endl 대신 \n을 사용하는 방법으로 입출력 효율성을 개선한 예시입니다.

• “2-F 시간 초과 질문”: 재귀 호출 최적화와 반복문으로의 변환에 대한 논의가 포함되어 있습니다.

위 정보를 바탕으로 코드의 효율성을 개선해 보시기 바랍니다. 유사한 문제를 해결한 다른 사용자의 답변이 도움될 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.