Bin_S+StudyRoom

• 문제

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

• 입력

첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

• 출력

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

• 예제 입력

2
lo3za4
01

4
43silos0
zita002
le2sim
231233

4
01bond
02james007
03bond
04austinpowers000

• 예제 출력

1
3
4

0
2
2
43
231233

0
1
2
3
4
7

• 접근방식

범위가 100글자니깐 int, long long 불가능, 문자열로 입력을 받아야함

입력을 받을때 아스키 코드를 활용하여 문자인지 숫자인지 확인, 숫자이면서 앞자리가 0이면 0을 지우기

• 코드

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

string s, ret;
int n;
vector<string> v;

void zero()
{
	while (1)
	{
		if (ret.size() && ret.front() == '0') // 맨앞이 0이면 0삭제
			ret.erase(ret.begin());
		else
			break;
	}

	if (ret.size() == 0)
		ret = "0"; // 결과가 0이면 비어있으니깐 0
	v.push_back(ret);
	ret = "";
}

bool compare(string a, string b) // 문자열 정렬을 하기 위함
{
	if (a.size() == b.size())
		return a < b;
	return a.size() < b.size();
}

int main() 
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> s;
		ret = "";
		for (int j = 0; j < s.size(); j++)
		{
			if (s[j] < 65) // 아스키코드 65(a) 이하면 숫자 이므로 그대로 결과 문자열에 붙임
				ret += s[j];
			else if (ret.size()) // 결과 문자열에서 0 지우기
				zero();
		}
		if (ret.size())
			zero();
	}
	sort(v.begin(), v.end(),compare);

	for (string a : v)
		cout << a << "\n";

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2870

• 문제

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다.

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

• 입력

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

• 출력

각 테스트 케이스를 '예제 출력'의 형태에 기반하여 품질을 평가하여라.

• 예제 입력

a
tv
ptoui
bontres
zoggax
wiinq
eep
houctuh
end

• 예제 출력

<a> is acceptable.
<tv> is not acceptable.
<ptoui> is not acceptable.
<bontres> is not acceptable.
<zoggax> is not acceptable.
<wiinq> is not acceptable.
<eep> is acceptable.
<houctuh> is acceptable.

• 접근방식

조건에 따라서 flag를 걸어 좋은 단어 인지 체크

조건1에 모음이 포함되어 있는지 확인하는 bool 변수 필요, 조건2에 모음 또는 자음이 3개 연속이면 안되니깐 글자를 한글자씩 세어 모음인지 자음인지에 따라 카운팅, 조건3에 같은 글자가 연속으로 오면 안되니깐 전 글자를 알 수 있는 변수 필요

• 코드

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

string s;
int vowelcnt, consonantcnt;

bool isvowl(int idx) // 모음이면 true 반환
{
	return (idx == 'a' || idx == 'e' || idx == 'i' || idx == 'o' || idx == 'u');
}

int main() 
{
	while (1)
	{
		cin >> s;

		if (s == "end")
			break;

		vowelcnt = 0;
		consonantcnt = 0;
		bool flag = 0;
		bool include_vowl = 0;
		int prev = -1;
		
		for (int i = 0; i < s.size(); i++)
		{
			int idx = s[i]; // 알파벳 하나를 검사

			if (isvowl(idx)) // 모음이 오면 모음 카운팅, 자음 카운팅 초기화, 모음 include true
				vowelcnt++, consonantcnt = 0, include_vowl = 1;
			else
				vowelcnt = 0, consonantcnt++; // 자음이면 자음 카운팅, 모음 카운팅 초기화
			if (vowelcnt == 3 || consonantcnt == 3) // 3번이상 모음이나 자음이 나오면 좋은 단어가 아님
				flag = 1;
			if (i >= 1 && (prev == idx) && (idx != 'e' && idx != 'o')) // s[i-1] s[i]를 비교할수도 있지만 
				flag = 1; // prev라는 변수로 전에 나온 문자 저장, i가 1이상 이여야하고(1글자 이상 나와야함)
							// e 와 o를 제외하고 같은 글자가 두번이상 나오면 좋은 문자가 아님

			prev = idx; // 반복문 끝에 문자를 저장
		}

		if (include_vowl == 0)
			flag = 1;
		if (flag)
			cout << "<" << s << ">" << " is not acceptable.\n";
		else
			cout << "<" << s << ">" << " is acceptable.\n";
	}
	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/4659

• 문제

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

• 입력

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

• 출력

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

• 예제 입력

5 2
2 1 2 1 2

9 3
1 3 3 3 2 2 2 1 1

9 77
11 33 11 77 54 11 25 25 33

• 예제 출력

2 2 2 1 1

1 1 1 3 3 3 2 2 2

11 11 11 33 33 25 25 77 54

• 접근방식

1순위로 정렬은 많이 나온수(카운팅), 2순위로 정렬은 먼저 나온수를 맵에 담아서 정렬

카운팅이 같을때 비교하는 함수 필요

• 코드

#include <iostream>
#include <algorithm>
#include <map>
#include <vector>

using namespace std;

int n, c, a[1004];
vector<pair<int, int>> v;
map<int, int> mp_cnt, mp_first;

bool compare(pair<int, int> a, pair<int, int> b) // 먼저 나온 순서를 비교하는 함수
{
	if (a.second == b.second) // 카운팅이 같으면
	{
		return mp_first[a.first] < mp_first[b.first]; // 번호가 먼저 나온 순서가 먼저
	}
	return a.second > b.second; // 카운팅 갯수
}

int main() 
{
	cin >> n >> c;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		mp_cnt[a[i]]++; // 나온 빈도수 카운팅
		if (mp_first[a[i]] == 0) // 한번도 나오지 않은 숫자라면 (맵은 인덱스에 참조만 해도 맵의 요소가 생김 int = 0, string = ""
			mp_first[a[i]] = i + 1; // 나온 순서 저장 ex) 3 3 3 2 2 2 면 첫번째 3이 나오면 1 저장, 두번째부터 3은 저장 X
									// 네번째로 나온 2는 4 저장
	}
	
	for (auto iter : mp_cnt)
	{
		v.push_back({ iter.first,iter.second }); // 나온 번호 , 카운팅을 벡터에 저장
	}

	sort(v.begin(), v.end(), compare);

	for (auto i : v)
	{
		for (int j = 0; j < i.second; j++)
		{
			cout << i.first << " ";
		}
	}

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2910

• 문제

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

• 입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

• 출력

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

• 예제 입력

5 1
3
1
5
3

5 2
3
1
5
3

• 예제 출력

6

4

• 접근방식

예시를 정확히 이해해야함, 바구니는 왼쪽과 오른쪽이 있으며 그 사이에 사과를 받아야함

오른쪽 끝점은 왼쪽 + M - 1 이라는걸 알아야함

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n, m, j, _left, _right, temp, ret;

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

	_left = 1;// 바구니의 왼쪽 부분은 1부터 시작

	for (int i = 0; i < j; i++)
	{
		cin >> temp; // 이동할 거리
		_right = _left + m - 1; // 오른쪽 부분은 왼쪽 + m - 1
		if (temp >= _left && temp <= _right) // 이미 바구니가 그 자리라면 이동하지않음
			continue;
		else
		{
			if (temp < _left) // 사과가 왼쪽에 떨어진 경우
			{
				ret += (_left - temp); // left - temp로 이동
				_left = temp; //left가 temp로 향함, right는 앞에서 다시 정의함
			}
			else // 사과가 오른쪽에 떨어진 경우
			{
				_left += (temp - _right); // left가 temp - right로 이동
				ret += (temp - _right); // temp - right로 이동, right는 앞에서 다시 정의함
			}
		}
	}
	cout << ret;

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2828

• 문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

• 출력

영상을 압축한 결과를 출력한다.

• 예제 입력

8
11110000
11110000
00011100
00011100
11110000
11110000
11110011
11110011

• 예제 출력

((110(0101))(0010)1(0001))

• 접근방식

재귀 함수를 이용해야함, 영역을 나눠서 탐색하며 끝나는 조건에 리턴을 하면서 영역을 계속 나눔,

• 코드

#include <iostream>
#include <algorithm>

using namespace std;

int n;
string s;
char _map[104][104];

string quard(int y, int x, int size)
{
	if (size == 1)
		return string(1, _map[y][x]); // 1밖에 없으면
	char b = _map[y][x];
	string ret = "";

	for (int i = y; i < y + size; i++)
	{
		for (int j = x; j < x + size; j++)
		{
			if (b != _map[i][j]) // 영역이 같지 않으면 4개로 나누면서 탐색
			{
				ret += '(';
				ret += quard(y, x, size / 2); // 2사분면 (왼쪽 위)
				ret += quard(y, x + size / 2, size / 2); // 1사분면 (오른쪽 위)
				ret += quard(y + size / 2, x, size / 2); // 3사분면 (왼쪽 아래)
				ret += quard(y + size / 2, x + size / 2, size / 2); // 4사분면 (오른쪽 아래)
				ret += ')';
				return ret;
			}
		}
	}
	return string(1, _map[y][x]);
}

int main() 
{
	cin >> n;

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

	cout << quard(0, 0, n);

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1992

• 문제

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

• 입력

첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오른쪽 위 꼭짓점의 x, y좌표값이 빈칸을 사이에 두고 차례로 주어진다. 모눈종이의 왼쪽 아래 꼭짓점의 좌표는 (0,0)이고, 오른쪽 위 꼭짓점의 좌표는(N,M)이다. 입력되는 K개의 직사각형들이 모눈종이 전체를 채우는 경우는 없다.

• 출력

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

• 예제 입력

5 7 3
0 2 4 4
1 1 2 5
4 0 6 2

• 예제 출력

3
1 7 13

• 접근방식

색칠하지 않은 부분인 연결된 컴퍼넌트 (Connected Component)를 구하는 문제, DFS를 사용하는데 int형 dfs를 사용해봄

• 코드

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

using namespace std;

#define y1 snrkdlrjfTma // y1이라는 변수를 라이브러리에서 사용하기 때문에 따로 정의해야함

int n, m, k;
int x1, x2, y1, y2;

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

vector<int> ret;

int _map[104][104], visited[104][104];

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

		if (ny < 0 || ny >= n || nx < 0 || nx >= m || visited[ny][nx] == 1)
			continue;
		if (_map[ny][nx] == 1)
			continue;
		ret += dfs(ny, nx);
	}
	return ret;
}

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

	for (int i = 0; i < k; i++)
	{
		cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++)
		{
			for (int y = y1; y < y2; y++)
			{
				_map[y][x] = 1; // 색칠하기
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			if (_map[i][j] == 0 && visited[i][j] == 0)
			{
				ret.push_back(dfs(i, j)); // 색칠하지 않은부분 dfs하고 사이즈 값을 vector에 넣어줌
			}
		}
	}

	sort(ret.begin(), ret.end());
	cout << ret.size() << "\n";
	for (auto a : ret)
		cout << a << " ";

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2583

• 문제

재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다. 

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다). 

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다. 

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다. 

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오. 

• 입력

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

• 출력

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

• 예제 입력

5
6 8 2 6 2
3 2 3 4 6
6 7 3 3 2
7 2 5 3 6
8 9 5 2 7

7
9 9 9 9 9 9 9
9 2 1 2 1 2 9
9 1 8 7 8 1 9
9 2 7 9 7 2 9
9 1 8 7 8 1 9
9 2 1 2 1 2 9
9 9 9 9 9 9 9

• 예제 출력

5

6

• 접근방식

연결된 컴퍼넌트 (Connected Component)를 구하는 문제, 높이를 1~101까지 반복해서 구한후 그 중에서 최대값을 구함

• 코드

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

using namespace std;

int n, ret = 0;

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

int _map[104][104], visited[104][104];

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

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

		if (ny < 0 || ny >= n || nx < 0 || nx >= n)
			continue;
		if (_map[ny][nx] > d && !visited[ny][nx]) // 높이보다 크고 방문처리가 안되어 있는 곳만 구함(안전영역)
			dfs(ny, nx , d);
	}
}

int main() 
{
	cin >> n;

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

	for (int d = 1; d < 101; d++)
	{
		memset(visited, 0, sizeof(visited)); // 높이마다 방문기록을 초기화
		int cnt = 0;
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if (_map[i][j] > d && !visited[i][j])
				{
					dfs(i, j, d);
					cnt++;
				}
			}
		}
		ret = max(ret, cnt); // 높이마다 나온 값중 최대값을 구함
	}

	cout << ret;

	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/2468

• 문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

• 입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

• 출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

• 예제 입력

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

1
5 3 6
0 2
1 2
2 2
3 2
4 2
4 0

• 예제 출력

5
1

2

• 접근방식

연결된 conneted Component를 찾는 문제, BFS, DFS 모두 가능하지만 DFS로 해결

• 코드

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

using namespace std;

int n, m, k, t, cnt, x, y;

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

int _map[104][104], visited[104][104];

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

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

		if (ny < 0 || ny >= n || nx < 0 || nx >= m)
			continue;
		if (_map[ny][nx] == 1 && !visited[ny][nx]) // 다음 방문할 곳이 1이고 방문되어 있지 않으면 그곳을 탐색
			dfs(ny, nx);
	}
}

int main() 
{
	cin >> t;

	while (t--)
	{
		memset(_map, 0, sizeof(_map)); // 테스트마다 _map과 visited를 0으로 초기화해서 찾아야함
		memset(visited, 0, sizeof(visited));

		cnt = 0;

		cin >> m >> n >> k;

		for (int i = 0; i < k; i++) // k개 만큼 좌표에 배추 심기
		{
			cin >> x >> y;
			_map[y][x] = 1;
		}

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

			}
		}
		cout << cnt << "\n";
	}


	return 0;
}

• 문제링크 : https://www.acmicpc.net/problem/1012