글 읽기 - 1012번 메모리 줄이기

tksgo2582 3년 전 0

안녕하세요. 다른 분들의 채점 결과를 보면

메모리차이가 거의 2배 정도 나서

질문드립니다.

혹시 지금 상태에서 메모리 사용을 좀 더 줄일 수 있는 방법이 있을까요??

배열을 동적으로 받는게 최선일까요?

#include <iostream>
#include <vector>
#include <string>

using namespace std;

#define MAX 51
#define MAX_location 2500

int cnt = 0;
int mat[MAX][MAX];
int visit[MAX][MAX];
int T;
int M, N, K;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void dfs(int x, int y) {
	visit[x][y] = 1;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];

		if (nx < 0 || nx >= M || ny < 0 || ny >= N)
			continue;
		if (mat[nx][ny] == 1 && visit[nx][ny] == 0)
			dfs(nx, ny);
	}
}

int main() {
	vector <int> v;
	cin >> T;
	while (T--) {
		cnt = 0;
		cin >> M >> N >> K;
		//테스트 케이스마다 배열 초기화
		for (int i = 0; i <= M; i++) {
			for (int j = 0; j <= N; j++) {
				mat[i][j] = 0;
				visit[i][j] = 0;
			}
		}
		// 배추가 있는 위치 입력
		for (int i = 0; i < K; i++) {
			int x, y;
			cin >> x >> y;
			mat[x][y] = 1;
		}
		// 배추가 있는 위치에서 dfs 시작
		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (mat[i][j] == 1 && visit[i][j] == 0) {
					cnt++;
					dfs(i,j);
				}
			}
		}
		v.emplace_back(cnt);
	}

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << "\n";
	}
}

otter66 3년 전 0

저는 이 문제를 풀 때 2차원배열 이외에는 변수 몇 개만 사용하여 풀었습니다.

동적으로 할당할 필요는 없다고 생각해요.

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

문제

문제

출처

ICPC

1012번 메모리 줄이기

tksgo2582 3년 전 0

otter66 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말