글 읽기 - 혼자 고민하다가 북극의 빙하가 먼저 녹아 제 집이 먼저 잠길 판입니다.

jjh63360 4년 전 0

안녕하세요.

식상한 문구지만, 다른 모든 분들과 같이 저도 게시판에 있는 반례들을 적용해 보았고,

제 코드가 반례들의 정답을 토해내기에 코딩 고수분들의 혜안을 얻고자 합니다.

더러운 코드지만 주석을 붙여놓았으니 이해하시기는 쉬울 것 같습니다.

같이 고민해주셔서 감사합니다.

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

int n,t,cnt;
int field[101][101];
int visited[101][101];
int dx[] = { 0,0,-1,1 };
int dy[] = { -1,1,0,0 };
queue<pair <int, int> > q;

//최대, 최소고도
int max_alti = 0, low_alti = 1000;
//visited 배열을 0으로 초기화 해줍니다.
void clear_visited();
//field에서 rainning 고도 보다 높은 지형을 찾아 동일 index의 visited배열을 cnt로 덮습니다.
void dfs(int rainning,int cnt);

int main()
{
	ios_base::sync_with_stdio(0);
	int ans=-1,temp;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		for (int j = 0; j < t; j++)
		{
			int temp;
			cin >> temp;
			temp > max_alti ? max_alti = temp : max_alti;
			temp < low_alti ? low_alti = temp : low_alti;
			field[i][j] = temp;
		}
	}
	//땅 높이가 같은지 체크합니다.
	if (low_alti == max_alti)
	{
		cout << 1;
		return 0;
	}

	for (int rainning = low_alti; rainning <= max_alti; rainning++)
	{
		clear_visited();
		cnt = 1;
		for (int i = 0; i < t; i++)
		{
			for (int j = 0; j < t; j++)
			{
				if (field[i][j] > rainning&&visited[i][j]==0)
				{
					q.push(make_pair(i, j));
					visited[i][j] = 1;
					//cnt변수로 홍수난 고도보다 높은 땅은 같은 cnt로 묶어줍니다.
					dfs(rainning,cnt++);	
				}
			}
		}
		ans < cnt ? ans = cnt : ans;
	}
	cout << ans-1;
	return 0;
}

void dfs(int rainning,int cnt)
{
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		for (int k = 0; k < 4; k++)
		{
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (0 <= nx && nx <= t && 0 <= ny && ny <= t)
			{
				if (field[nx][ny] > rainning&&visited[nx][ny]==0) 
				{
					visited[nx][ny] = cnt;
					q.push(make_pair(nx, ny));
				}
			}
		}
	}
}

void clear_visited()
{
	for (int i = 0; i < t; i++)
	{
		for (int j = 0; j < t; j++)
		{
			visited[i][j] = 0;
		}
	}
}

shg9411 4년 전 1

76번라인 확인바랍니다.

shg9411 4년 전 1

dfs가 아니라 bfs를 사용하신 것 같고요

jjh63360 4년 전 0

헉 bfs로 짜야지~ 하면서 함수명을 dfs로 해놨네요.

지적 감사합니다. 76번째 줄 확인해보겠습니다. 감사합니다.

jjh63360 4년 전 1

지적해주신 76번째줄 수정하니 맞았습니다.

고민해주셔서 감사합니다.

if (0 <= nx && nx < t && 0 <= ny && ny < t)

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

문제

문제

출처

ICPC

혼자 고민하다가 북극의 빙하가 먼저 녹아 제 집이 먼저 잠길 판입니다.

jjh63360 4년 전 0

shg9411 4년 전 1

shg9411 4년 전 1

jjh63360 4년 전 0

jjh63360 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말