2024 - 07 - 18 C++ 코딩테스트 10주완성 D+18

 

백준 2468 문제 - 안전 영역

 

2차원 정사각형 행렬안에서 물에 잠기는 기준높이(1 이상~100 이하) n 초과일 경우들의 원소들의 집합개수를 구하고 그중에서 최대의 개수를 구하여라

 

입력

 

2차원 정사각형 행과 열의 개수를 나타내는 수 N 을 입력받는다.

각 줄마다 2차원 배열의 첫번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보를 입력받는다.

 

출력

 

안전 영역의 최대 개수를 출력하여야 한다.

 

수정전 실습코드

#include <bits/stdc++.h>

using namespace std;

const int max_n = 104;

//2차원 배열
int a[max_n][max_n];

int visited[max_n][max_n];

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

int ux, uy,n,max_h,min_h;
int ret[max_n];


//연결된 컴포넌트 DFS 필요



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

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

        if (uy >= n || uy < 0 || ux >= n || ux < 0)
        continue;

        if (a[uy][ux] > h && !visited[uy][ux])
        dfs(uy, ux,h);
    }
	return;
}

int main()
{
    cin >> n;

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

        if (i == 0 && j == 0)
        min_h = a[i][j];

        else if (a[i][j] > max_h)
        max_h = a[i][j];

        else if (a[i][j] < min_h)
        min_h = a[i][j];

        }
    }

    for (int height = min_h; height < max_h; height++)
    {
        fill(&visited[0][0], &visited[0][0] + max_n * max_n, 0);
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!visited[i][j] && a[i][j] > height)
                {
                    dfs(i, j, height);
                    ret[height]++;
                }
            }
        }
        if (ret[0] < ret[height])
        ret[0] = ret[height];
    }

    cout << ret[0];



    return 0;
}

분명 예제에는 나와야하는 출력값이 나와서 정답인줄 알았는데
백준에 제출하니

라고 뜬다...

뭐가 문젠지 몰라서 인프런 강의를 찾아보니, 백준문제의 조건중..

 

이라는 조건이 있었고, 이 뜻은 1부터 100까지의 경우의 수를 전부 구해야 조건을 만족한다는 말이였다..!!

이 코드를 수정하고 제출을 해보니

 

시 원...    오늘도 하나 배워간다..!!

 

수정한 실습코드

 

#include <bits/stdc++.h>

using namespace std;

const int max_n = 104;

//2차원 배열
int a[max_n][max_n];

int visited[max_n][max_n];

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

int ux, uy,n;
int ret[max_n];


//연결된 컴포넌트 DFS 필요



void dfs(int y, int x,int h)
{
	visited[y][x] = 1;
	
	for (int i = 0; i < 4; i++)
	{
		uy = y + dy[i];
		ux = x + dx[i];

		if (uy >= n || uy < 0 || ux >= n || ux < 0)
			continue;

		if (a[uy][ux] > h && !visited[uy][ux])
			dfs(uy, ux,h);
		
		
	}



	return;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];						
		}
	}

	for (int height = 0; height < 100; height++)
	{
		fill(&visited[0][0], &visited[0][0] + max_n * max_n, 0);
		for (int i = 0; i < n; i++)
		{			
			for (int j = 0; j < n; j++)
			{
				if (!visited[i][j] && a[i][j] > height)
				{
					dfs(i, j, height);
					ret[height]++;
				}
			}
		}
		if (ret[0] < ret[height])
			ret[0] = ret[height];
	}

	cout << ret[0];
	return 0;
}

---

 

 

백준 2583 - 영역 구하기

MxN 크기의 행렬안에 K개의 직사각형을 그릴때 K개의 직사각형 내부를 제외한 나머지의 영역의 개수와 넓이를 구하여라

 

 

입력 

 

첫째 줄에 M과 N 그리고 K 가 빈칸을 사이에 두고 차례로 주어진다.
M 은 행의 개수 N 은 열의 개수, K 는 직사각형의 개수이다.
둘째 줄에 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x,y 좌표값과 오른쪽 위 꼭짓점의 x,y 좌표값이 빈칸을 사이에 두고 차례로 주어진다.
(단, 모눈종이 왼쪽 아래의 꼭짓점 좌표는 (0,0) 오른쪽 위 꼭짓점의 좌표는 (N,M)이다.)

 

출력

첫째 줄에 분리되어 나누어지는 영역의 개수를 출력한다. 
둘째 줄에는 각 영역의 넓이를 오름차순으로 정렬하여 빈칸을 사이에 두고 출력한다.

 

실습코드

 

#include <bits/stdc++.h>

using namespace std;

const int max_n = 104;

int a[max_n][max_n], visited[max_n][max_n];

int dy[] = { -1, 0, 1 , 0 };

int dx[] = { 0, 1, 0, -1 };

int m, n, k, nx, ny, lx, ly, rx, ry;

vector<int> ret;

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

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

        if (!a[ny][nx] && !visited[ny][nx])
        {
            ret += dfs(ny, nx);
        }
}

return ret;
}

int main()
{
cin >> m >> n >> k;

for (int i = 0; i < k; i++)
{
    cin >> lx >> ly >> rx >> ry;

    for (int j = lx; j < rx; j++)
    {
        for (int e = ly; e < ry; e++)
        {
            a[e][j] = 1;
        }
    }
}

for (int i = 0; i < m; i++)
{
    for (int j = 0; j < n; j++)
    {
        if (!visited[i][j] && !a[i][j])
        {
            ret.push_back(dfs(i, j));

        }
    }
}

sort(ret.begin(),ret.end());

cout << ret.size() << endl;

for (int i : ret)
{
    cout << i << " ";
}
return 0;

}

 

이번에는 백준 예제입력을 넣고 출력해보았더니, 예제출력이 나오지 않고 엉뚱한 숫자만 나왔다.

왜그러지....하며 고민하다가 결국 강의에 들어가서 강의코드랑 비교해보니

 

직사각형안의 원소들에 값을 적어놓는 조건문에 문제가 있었다!

원래 내가 생각하던 원소 값을 집어넣는 범위는 당연히 직사각형을 만드는 것이니,

왼쪽 밑 꼭지점(X,Y) 이상 오른쪽 위 꼭짓점 (X,Y) 이하까지 원소에 값을 집어넣는 것이였는데,

그렇게 되면 기존 직사각형의 가로세로 각각 +1 인 직사각형의 넓이를 구하게 되는 것이므로 헷갈린것이다..

배열의 인덱스 번호와 좌표값을 혼동해서 생긴 문제이다.. ㅠ

오른쪽 위 꼭지점을 이하가 아닌 미만으로 변경하니 잘 해결되었다...

수정된 코드

 

#include <bits/stdc++.h>

using namespace std;

const int max_n = 104;

int a[max_n][max_n], visited[max_n][max_n];

int dy[] = { -1, 0, 1 , 0 };

int dx[] = { 0, 1, 0, -1 };

int m, n, k, nx, ny, lx, ly, rx, ry;

vector<int> ret;

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

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

		if (!a[ny][nx] && !visited[ny][nx])
		{
			ret += dfs(ny, nx);
		}
	}

	return ret;
}

int main()
{
	cin >> m >> n >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> lx >> ly >> rx >> ry;

		for (int j = lx; j < rx; j++)
		{
			for (int e = ly; e < ry; e++)
			{
				a[e][j] = 1;
			}
		}
	}

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (!visited[i][j] && !a[i][j])
			{				
				ret.push_back(dfs(i, j));
				
			}
		}
	}

	sort(ret.begin(),ret.end());

	cout << ret.size() << endl;

	for (int i : ret)
	{
		cout << i << " ";
	}
	return 0;

}