[백준 2573] 빙산

문제 바로가기

2573번: 빙산

 

BFS로 풀었다.

문제 읽고 정말 빨리 풀 수 있을 줄 알았는데..

처음 제출하고 시간초과 떠서 2중 for문 하나 지우려고 삽질 오지게 했다

어차피 그거 지워도 시간복잡도 똑같잖아 멍처아 !!!!!!!!

 

memset 바꾸고 vector도 배열로 바꾸고 오만짓 다해봤는데 계속 58%에서 시간초과 ㅠ

 

알고보니 모든 map의 값이 0인지 확인하는 변수를 전역변수로 선언해서였다

앞으로 이런 실수는 하지말자

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
#include <vector>

using namespace std;

int N, M;
int map[301][301];
int melting[301][301];
int visited[301][301];

int year = 0;
int pos[4][2] = { {1,0}, {-1,0}, {0,1}, {0,-1} };


void bfs(int y, int x)
{
	queue<pair<int, int>> Q;
	Q.push(make_pair(x, y));
	visited[y][x] = 1;

	while (!Q.empty())
	{
		int cx = Q.front().first;
		int cy = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = cx + pos[i][1];
			int ny = cy + pos[i][0];

			if (map[ny][nx] > 0 && visited[ny][nx] == 0)
			{
				visited[ny][nx] = 1;
				Q.push(make_pair(nx, ny));
			}
		}
	}
}

int main()
{
	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= M; j++)
		{
			cin >> map[i][j];
		}
	}

	while (1)
	{
		int cnt = 0;
		int flag = 0;
		year++;

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				if (map[i][j] > 0)
				{
					int melt = 0;
					for (int k = 0; k < 4; k++)
					{
						int nx = j + pos[k][1];
						int ny = i + pos[k][0];

						if (map[ny][nx] == 0)
						{
							melt++;
						}
					}
					melting[i][j] = melt;
				}
			}
		}

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				if (map[i][j] > 0)
				{
					flag = 1;
					map[i][j] -= melting[i][j];
					if (map[i][j] < 0)
						map[i][j] = 0;
				}
			}
		}

		if (flag == 0)
		{
			year = 0;
			break;
		}

		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= M; j++)
			{
				if (map[i][j] > 0 && !visited[i][j])
				{
					bfs(i, j);
					cnt++;
				}
			}
		}

		if (cnt >= 2)
			break;

		memset(melting, 0, sizeof(melting));
		memset(visited, 0, sizeof(visited));
	}

	cout << year << endl;
}