글 읽기 - 유기농 배추 문제 런타임에러입니다 ㅠㅠ...

skfnxh0124 6년 전 0

그래프써서 풀어보고 싶어서. 메모리는 많이사용하겠지만

2차원 배열의 인접정보를 그래프로 표현했습니다.

어느쪽이 문제인지 알려주세요.

추가로. 2차원 배열의 인접정보를 그래프화 하는 방법중에 좋은 방법있을까요?

- 제 코드가 세로가 길이가 더 길때 문제가 생길까요 ..?

// vector 자료구조를 이용해서 다 넣고 그래프로 바꾼다.
// 그 후에 전체 vector를 탐색하면서 체크하지 않은곳을 dfs를 할 것이다.
// dfs시작하면 인접한곳은 다체크가 되기 때문에 정확한 집단을 구할 수 있다.
// 전체배열의 크기 50*50, 탐색 2초안에 가능
// 시간복잡도 문제는 없을 듯

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int cnt = 0;

class Graph {
public:
	int N;
	vector<vector<int>>adj;
	vector<bool> visited;

	Graph() :N(0) {}
	Graph(int n) :N(n) {
		adj.resize(N);
		visited.resize(N);
	}
	void addEdge(int u, int v)
	{
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	void init_() {
		fill(visited.begin(), visited.end(), false);
	}

	void dfs(int curr) {
		visited[curr] = true;
		for (int next : adj[curr])
			if (!visited[next])
				dfs(next);
	}
};

int main()
{
	int test_case;
	cin >> test_case;
	int M, N;
	int K;
	int temp_u, temp_v;
	int **ptr;
	while (test_case)
	{
		cin >> M >> N >> K;
		int temp;
		
		if (M > N)
			temp = M;
		else
			temp = N;
		Graph G(M*N);
		ptr = new int*[M];
		for (int i = 0; i < M; i++)
			ptr[i] = new int[N];
		for (int i = 0; i < M; i++)
			for (int j = 0; j < N; j++)
				ptr[i][j] = 0;
		while (K)
		{
			cin >> temp_u >> temp_v;
			ptr[temp_u][temp_v] = 1;
			K--;
		}
		
		//그래프화! 만 하면 끝
		for (int i = 0; i < M - 1; i++)
			for (int j = 0; j < N - 1; j++)
			{
			
				if (ptr[i][j] == 1 && ptr[i + 1][j] == 1)
					G.addEdge(N*i + j, N*(i + 1) + j);
				if (ptr[i][j] == 1 && ptr[i][j + 1] == 1)
					G.addEdge(N*i + j, N*i + j + 1);
				
			}
		if (ptr[M - 1][N - 1] == 1)
		{
			if(	ptr[M-1-1][N-1]==1)
				G.addEdge(N*(M - 1) + N - 1,N*(M - 2) + N - 1);
			if(ptr[N-1][M-1-1]==1)
				G.addEdge(N*(M - 1) + N - 1, N*(M - 1) +N - 1-1);
		
		}


		//그래프화
		G.init_();
		for (int i = 0; i < M*N; i++)
		{
			for (int next : G.adj[i])
			{
				if (G.visited[next] == false)
				{
					G.dfs(next);
					cnt++;
				}
			}
		}
		for (int i = 0; i <M;i++)
			for (int j = 0; j < N; j++)
			{
				if (ptr[i][j] == 1 && G.visited[N*i + j] == false)
					cnt++;
			}
			
		cout << cnt << endl;
		cnt = 0;

		test_case--;
	}
}

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

문제

문제

출처

ICPC

유기농 배추 문제 런타임에러입니다 ㅠㅠ...

skfnxh0124 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말