글 읽기 - c++ 시간초과 고수님들 도와주세요ㅠㅠ

tinea17 3년 전 0

main 함수에서 전체배열 north 선언, 방문배열 visited 선언하고

전체배열 입력받을때 빙산이 아닌 부분은 -1로 초기화했습니다.

그리고 while 무한루프 안에서

1) 매년 빙산 녹을때마다(melt함수 실행) time 1씩 증가

2) 1년 후 빙산 덩어리 갯수 세기 위해 dfs 실행

3) cnt가 2이상일 경우 무한루프 종료, cnt가 1일 경우 다시 처음부터 반복, cnt가 0일 경우 0출력하고 종료

4) visited배열 false로 초기화

이렇게 했을때 테케는 통과하는데 시간초과가 납니다..ㅠㅠ 어느 부분을 바로잡으면 될지 알려주시면 감사하겠습니다,,

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

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

// 빙산 녹이기
void melt(vector<vector<int>>& north)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (north[i][j] >= 0)	// 빙산 부분
			{
				int cnt = 0;
				for (int dir = 0; dir < 4; dir++)
				{
					int nx = i + dx[dir];
					int ny = j + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
					if (north[nx][ny] == -1) cnt++;
				}

				north[i][j] = north[i][j] - cnt < 0 ? 0 : north[i][j] - cnt;
			}
		}
	}
}

// 빙산덩어리 갯수 세기 -> 일반적인 dfs탐색
void dfs(int x, int y, vector<vector<int>>& north, vector<vector<bool>>& visited)
{
	if (visited[x][y]) return;

	visited[x][y] = true;

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

		if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
		if (north[nx][ny] <= 0) continue;

		dfs(nx, ny, north, visited);
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	vector<vector<int>> north(n, vector<int>(m, 0));
	vector<vector<bool>> visited(n, vector<bool>(m, false));

	for (int i=0; i<n; i++)
	{
		for (int j=0; j<m; j++)
		{
			cin >> north[i][j];

			if (north[i][j] == 0)
				north[i][j] = -1;
		}
	}

	int time = 0;
	while (1)
	{
		melt(north);
		time++;

		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (north[i][j] > 0 && !visited[i][j])
				{
					dfs(i, j, north, visited);
					cnt++;
				}
			}
		}

		if (cnt >= 2) break;
		else if (cnt == 0)
		{
			cout << 0;
			return 0;
		}

		for (int i=0; i<n; i++)
			fill(visited[i].begin(), visited[i].end(), false);
	}
	
	cout << time;
}

tinea17 3년 전 0

코드 수정했습니다.

시간초과 나는 이유가 배열을 입력받으면서 동시에 0인 부분을 -1로 초기화 시켜주는 부분인 56, 57 라인 때문에 시간초과가 나는 건 아닐까 싶은데.. 알려주시면 감사하겠습니다!

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

int n, m;

// 빙산 녹이기 -> BFS 탐색 (BFS 한번 실행될 때마다 1년 경과)
void bfs(int x, int y, vector<vector<int>>& north, vector<vector<bool>>& visited)
{
	int dx[4] = { 1,0,-1,0 };
	int dy[4] = { 0,1,0,-1 };

	queue<pair<int, int>> q;
	q.push({x, y});
	visited[x][y] = true;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();

		int cnt = 0;
		for (int dir = 0; dir < 4; dir++)
		{
			int nx = cur.first + dx[dir];
			int ny = cur.second + dy[dir];

			if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
			if (north[nx][ny] == -1)							// 바닷물일 경우
			{	// 바닷물과 맞닿은 면 갯수만큼 빙산높이 감소 -> 빙산높이는 0보다 작지않다
				north[cur.first][cur.second] = north[cur.first][cur.second] - 1 < 0 ? 0 : north[cur.first][cur.second] - 1;
			}
			else if (north[nx][ny] > 0 && !visited[nx][ny])		// 아직 방문하지 않은 빙산일 경우
			{
				q.push({nx, ny});
				visited[nx][ny] = true;
			}
		}
	}
}

int main()
{
	cin >> n >> m;
	vector<vector<int>> north(n, vector<int>(m, 0));
	vector<vector<bool>> visited(n, vector<bool>(m, false));

	for (int i=0; i<n; i++)
	{
		for (int j=0; j<m; j++)
		{
			cin >> north[i][j];

			if (north[i][j] == 0)
				north[i][j] = -1;
		}
	}

	int time = 0;
	while (1)
	{
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < m; j++)
			{
				if (north[i][j] > 0 && !visited[i][j])
				{
					bfs(i, j, north, visited);
					cnt++;
				}
			}
		}

		if (cnt >= 2) break;
		else if (cnt == 0)
		{
			cout << 0;
			return 0;
		}

		time++;
		for (int i=0; i<n; i++)
			fill(visited[i].begin(), visited[i].end(), false);
	}
	
	cout << time;
}

lta1204 3년 전 0

제 눈에만 종료 조건이 안보일까요?

문제 보면 '빙하가 없어질 때 까지, 한 덩어리 이상으로 안 나눠지면 0이다 라고나와있지만, 그부분 어디있을까요?

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

문제

문제

출처

ICPC

c++ 시간초과 고수님들 도와주세요ㅠㅠ

tinea17 3년 전 0

tinea17 3년 전 0

lta1204 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말