관심이 가는 개발 보물창고

풀이

약간 도미노를 생각하면 편할 것 같다.

왼쪽부터 간다고 생각하면 다음과 같다.

3 ~ 4 의 구간은 비록 높이가 0인 다각형이지만 2 ~ 3 구간에서의 높이가 4이기 때문에 3 ~ 4 구간의 높이도 4가 된다.

5 ~ 6 의 구간은 비록 높이가 3인 다각형이지만 4 ~ 5 구간에서의 높이가 6이기 때문에 5 ~ 6 구간의 높이도 6이 된다.

즉 나보다 한 칸 옆에서의 높이가 나의 높이보다 크다면 그것으로 갱신해준다.

	for (int i = 1; i <= 1000; i++)
		area[i] = max(height[i], area[i - 1]);

오른쪽부터 간다고 생각하면 다음과 같다.

15 ~ 16 구간은 높이가 8인 다각형이지만 현재 area 는 10으로 되어있다. 따라서 더 작은 값으로 갱신하면 된다.

14 ~ 15 구간을 보자.

높이가 0인 다각형이지만 현재 area 는 10으로 되어있다.

문제에 따르면 이 구간의 높이는 8이 되야한다.

한 칸 오른쪽에서의 넓이 area가 현재 높이보다 크다면 더 큰 값인 10으로 갱신한다.

그리고 나서 현재 area 와 비교해서 더 작은 값으로 갱신하면 8이 된다.

7 ~ 8 구간을 보자.

현재의 높이는 0이고, 한 칸 오른쪽에서의 넓이 area가 현재 높이보다 크다면 더 큰 값인 10으로 갱신한다.

그리고 나서 현재 area와 비교해서 더 작은 값으로 갱신하면 6이 된다.

	for (int i = 1000; i >= 0; i--)
		area[i] = min(area[i], max(height[i], area[i + 1]));

왼쪽과 오른쪽을 통해서 얻은 area 를 다 더해주면 창고 다각형의 넓이를 구할 수 있게 된다.

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

int n;
int height[1001];
int area[1001];
int main()
{
	cin >> n;
	while (n--)
	{
		int L, H;
		cin >> L >> H;
		height[L] = H;
	}

	// left
	for (int i = 1; i <= 1000; i++)
		area[i] = max(height[i], area[i - 1]);

	// right
	for (int i = 1000; i >= 0; i--)
		area[i] = min(area[i], max(height[i], area[i + 1]));

	int ret = 0;
	for (int i = 1; i <= 1000; i++)
		ret += area[i];

	cout << ret << '\n';
	return 0;
}

특징

1. 자동적으로 정렬되지 않는다.

2. hash 사용으로 bucket 으로 인해 메모리 사용량 증가

3. insertion, deletion, find O(1)에 수행, 다만 충돌이 너무 많이 일어나면 O(N)

(그러면 기존 set 보다 더 느리게 수행될 수 있다는 말이다.)

4. hash 자료구조를 사용한다.

원소의 개수가 많을수록 해시 충돌이 일어날 확률도 많아지게 되므로

경우에 따라 사용하자.

원소의 개수가 적고 빠른 성능 : unordered_set

원소의 개수가 많고 안정성 : set

Hash function

정의는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.

unordered_set 에 특정 value 를 찾거나 넣을 때 해당 value 를 hash function 에 넣고 나온 리턴 값인

hash value 를 얻는다.

기본적으로  hash value 는 bucket 에 들어가는 index 보다 크기 때문에 bucket 의 size 로 나머지 연산을 하여서 최종 index 를 얻고 그 bucket[index] 에 해당 value 를 저장하게 된다.

1. value -> hash function -> hash value(해시 값)

2. hash value % bucket count = index

3. bucket[index] 에 linked list 로 value 를 넣어준다.

이때 서로 다른 value 라도 우연히 hash value 가 같을 수 있는데

이를 hash collision(해시 충돌)이라고 한다.

O(1) ??

insertion, deletion, find 가 어떻게 O(1)이 나올까?

문자열 "abc" 를 unordered_set 에 삽입한다고 하면.

1. "abc" 는 hash function 으로 리턴 값인 hash value : 23103023124 를 얻는다. O(1)

2. hash value % bucket count = 4 (index) O(1)

3. bucket[4] -> "abc" (Linked List에 삽입은 O(1))

따라서 insertion 은 O(1) 에 가능하다.

문자열 "abc" 를 unordered_set 에서 찾거나 삭제한다면?

1. "abc" 는 hash function 으로 리턴 값인 hash value : 23103023124 를 얻는다. O(1)

2. hash value % bucket count = 4 (index) O(1)

3. bucket[4] 에서 "abc" 찾는다.  O(1)

따라서 find, deletion 도 O(1) 에 가능하다.

그런데, element 가 너무 많아지게 되면 hash collision 이 빈번하게 발생하여

서로 다른 값임에도 불구하고 같은 bucket 에 연결된다면 O(N) 이 아닐까?

element 가 많아지게 되면 hash 자체 내부에서 rehashing 이 일어나 bucket count 를 늘려 O(1) 에 수행할 수 있게 변경된다. 다만 rehashing 의 경우 O(N) 이 소요되기 때문에 이를 막기 위해 선언할 때

reserve 를 활용하여 rehashing 의 빈도수를 줄일 수 있다.

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
	unordered_set<string> s;

	s.insert("abc");
	s.insert("def");
	s.insert("ghi");
	s.insert("jkl");

	// string(input) -> hash function -> hash value
	cout << "abc: " << hash<string>{}("abc") << endl;
	cout << "def: " << hash<string>{}("def") << endl;
	cout << "ghi: " << hash<string>{}("ghi") << endl;
	cout << "jkl: " << hash<string>{}("jkl") << endl << endl;

	// hash value % bucket_count -> index(hash table mapping)
	cout << "bucket count : " << s.bucket_count() << endl;
	cout << "abc bucket : " << s.bucket("abc") << endl;
	cout << "def bucket : " << s.bucket("def") << endl;
	cout << "ghi bucket : " << s.bucket("ghi") << endl;
	cout << "jkl bucket : " << s.bucket("jkl") << endl << endl;

	// 더 많은 input이 들어오면, rehashing이 발생한다.
	// rehashing 은 O(N)이 소모되므로,
	// 이를 방지하고자 할 때 미리 할당해주는 reserve 를 사용한다.
	s.insert("dasq");
	s.insert("dasdawq");
	s.insert("rdewq");
	s.insert("vkbas");
	s.insert("treq");
	s.insert("gfoas");
	s.insert("bdea");
	s.insert("dela");
	s.insert("jgela");
	cout << "bucket count : " << s.bucket_count() << endl;
	return 0;
}

abc: 440920331
def: 3310976652
ghi: 992499321
jkl: 3286144074

bucket count : 8
abc bucket : 3
def bucket : 4
ghi bucket : 1
jkl bucket : 2

bucket count : 64

참고:)

youtu.be/MsDz50o3jHY

특징

set의 경우 key 값이 중복되지 않지만,

multiset의 경우 key 값이 중복될 수 있다.

대부분의 특징들은 set과 동일하므로 바로 예제를 통해서 하나씩 배워보자.

삽입

set과 마찬가지로 insert(key); 를 이용해서 삽입할 수 있다.

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

int main()
{
	multiset<int> ms;
	// less <
	// left node < parent node <= right node
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	auto iter = ms.insert(10); // 저장된 위치만 가리키는 반복자 리턴

	cout << "*iter : " << *iter << '\n';

	for (iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	// greater >
	// left node >= parent node > right node
	multiset<int, greater<int>> ms2;
	for (iter = ms.begin(); iter != ms.end(); iter++)
		ms2.insert(*iter);

	for (iter = ms2.begin(); iter != ms2.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	return 0;
}

*iter : 10
10 30 30 50 70 80 80
80 80 70 50 30 30 10

다양한 검색 연산들

count(key) : key가 몇 개 있는지 리턴

find(key) : key의 반복자를 리턴, 없다면 end() 리턴

lower_bound(key) : 찾는 key의 시작 반복자 리턴

upper_bound(key) : 찾는 key의 다음 반복자 리턴

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

int main()
{
	multiset<int> ms;
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	ms.insert(10);

	for (auto iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	cout << "ms.count(30) : " << ms.count(30) << '\n';
	cout << "ms.count(100) : " << ms.count(100) << '\n';

	auto iter = ms.find(30);
	if (iter != ms.end())
		cout << "30 exist\n";
	else
		cout << "30 not exist\n";

	iter = ms.find(100);
	if (iter != ms.end())
		cout << "100 exist\n";
	else
		cout << "100 not exist\n";

	multiset<int>::iterator lower_iter;
	multiset<int>::iterator upper_iter;

	lower_iter = ms.lower_bound(30);
	upper_iter = ms.upper_bound(30);
	cout << "lower_iter : " << *lower_iter << '\n';
	cout << "upper_iter : " << *upper_iter << '\n';

	cout << "[lower_iter, upper_iter) -> ";
	for (iter = lower_iter; iter != upper_iter; iter++)
		cout << *iter << ' ';
	cout << '\n';
	return 0;
}

10 30 30 50 70 80 80
ms.count(30) : 2
ms.count(100) : 0
30 exist
100 not exist
lower_iter : 30
upper_iter : 50
[lower_iter, upper_iter) -> 30 30

equal_range()

lower_bound와 upper_bound를 따로 찾을 필요 없이 한 쌍으로 리턴해준다.

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

int main()
{
	multiset<int> ms;
	ms.insert(50);
	ms.insert(30);
	ms.insert(80);
	ms.insert(80);
	ms.insert(30);
	ms.insert(70);
	ms.insert(10);

	for (auto iter = ms.begin(); iter != ms.end(); iter++)
		cout << *iter << ' ';
	cout << '\n';

	auto iter = ms.equal_range(30);
	for (auto p = iter.first; p != iter.second; p++)
		cout << *p << ' ';
	cout << '\n';
	return 0;
}

10 30 30 50 70 80 80
30 30

다양하게 연습해보기

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

int main()
{
	multiset<int, greater<int> > mset;
	multiset<int, greater<int> > ::iterator itr;

	mset.insert(40);
	mset.insert(40);
	mset.insert(40);
	mset.insert(30);
	mset.insert(60);
	mset.insert(20);
	mset.insert(50);
	mset.insert(50);
	mset.insert(10);

	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "Size : " << mset.size() << endl;

	cout << "[mset.begin(), mset.find(40)) erase\n";
	mset.erase(mset.begin(), mset.find(40));

	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "40 counts : " << mset.count(40) << endl;

	cout << "Max-Size : " << mset.max_size() << endl;

	cout << "erase 40\n";
	mset.erase(40);
	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	mset.clear();

	mset = { 1,2,3,4,5,5,5,3,3,9,10 };
	cout << "mset : ";
	for (itr = mset.begin(); itr != mset.end(); ++itr)
		cout << *itr << ' ';
	cout << endl;

	cout << "lower_bound(5) : " << *mset.lower_bound(5) << endl;
	cout << "upper_bound(5) : " << *mset.upper_bound(5) << endl;
	for (auto i = mset.lower_bound(5); i != mset.upper_bound(5); ++i)
		cout << *i << ' ';
	cout << endl;

	auto p = mset.equal_range(5);
	for (auto i = p.first; i != p.second; ++i)
		cout << *i << ' ';
	cout << endl;
	return 0;
}

mset : 60 50 50 40 40 40 30 20 10
Size : 9
[mset.begin(), mset.find(40)) erase
mset : 40 40 40 30 20 10
40 counts : 3
Max-Size : 214748364
erase 40
mset : 30 20 10
mset : 10 9 5 5 5 4 3 3 3 2 1
lower_bound(5) : 5
upper_bound(5) : 4
5 5 5
5 5 5

풀이

stack 자료구조를 사용하면 쉽게 해결할 수 있다.

줄이 1 ~ 6이므로 stack을 배열처럼 사용하면 여러 개의 stack 줄이 생기게 된다.

현재 top과 치려고 하는 프렛의 번호를 비교해서 count를 매기면 된다.

치려고 하는 프렛의 번호를 b라고 하면

top() > b 이면,

pop 해주고 count++

top() == b이면,

굳이 손을 다른 프렛으로 옮기지 않아도 되므로 패스

top() < b이면,

push 하고 count++

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

int n, p;
stack<int> st[7];

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

	cin >> n >> p;

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		while (1)
		{
			if (st[a].empty())
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() < b)
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() == b)
				break;
			else if (!st[a].empty() && st[a].top() > b)
			{
				st[a].pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

스택의 응용 중 하나인 후위 표기식에 대해서 배워보자.

후위 표기식

우리가 자주 사용하는 표기식은 중위 표기식(infix expression)을 따른다.

5 + 3

후위 표기식(postfix expression)은 연산자가 피연산자 뒤에 나오는 것을 말한다.

5  3 +

후위 표기식 계산법

7 4 -3 * 1 5 + / * 

스택 자료구조를 이용해서 계산할 수 있다.

핵심은 두 수를 뽑을 때의 순서가 중요하다.

방법은 다음과 같다.

1) 피연산자(즉, 숫자)가 들어오면 무조건 출력

2) 연산자가 들어오면 스택의 최상단에서 두 값을 뽑아 연산자에 맞게 계산하고 다시 스택에 넣어준다.

단계별로 확인해보자.

input : 7 4 -3 * 1 5 + / * 

중위 표기식을 후위 표기식으로 변환 (괄호가 없는 ver.)

조금 더 깊게 들어가 보자.

우리가 잘 알고 있는 중위 표기식을 후위 표기식으로 어떻게 변환할까?

=> 스택 자료구조를 사용하여 해결할 수 있다.

풀어쓰면 다음과 같다.

1) 중위 표기식을 처음부터 순서대로 읽으면서 피연산자는 즉시 출력한다.

2) 모든 연산자는 일단 스택에 push 한다.

단, 이때 스택 내에 우선순위가 자신보다 더 높은 연산자가 있다면 pop 하여 출력하고

이후 push 한다. 여기서 더 높은 연산자는 정말로 높은 우선순위 연산자일 수도 있고,

혹은 우선순위가 같은 연산자도 먼저 들어온 연산자가 더 높은 우선순위를 가지게 된다.

핵심 방법은 다음과 같다.

1) 피연산자는 출력한다.

2) 연산자라면 아래와 같이 고려한다.

2-1) stack.top() < 들어오는 연산자이면, 들어오는 연산자를 스택에 push 한다.

2-2) stack.top() >= 들어오는 연산자이면, 이 조건에 맞는 연산자들은 다 pop 하여

결과에 추가하고, 들어오는 연산자를 스택에 push 한다.

단계별로 확인해보자.

input : 2 - 10 / 5 * 6 + 4

중위 표기식을 후위 표기식으로 변환 (괄호가 있는 ver.)

그렇다면 괄호가 있으면 어떻게 처리할까?

핵심 방법은 다음과 같다.

1) 여는 괄호가 있으면 무조건 스택에 push 한다.

2) 닫는 괄호가 나오면 스택에서 여는 괄호가 나올 때까지 pop 하여 출력하고,

마지막 여는 괄호도 pop 해준다, 이때 닫는 괄호는 스택에 push 하지 않는다.

단계별로 확인해보자.

input : 3 + ( ( 4 * 7 ) / 2 )

참고:)

YouTube

풀이

이 문제는 그림을 그리면서 살펴봐야 쉽게 풀 수 있다.

아래 그림을 보면,

가장 위에 있는 숫자는 현재 막대기의 수를 의미한다.

아래의 숫자는 현재 레이저로 쐈을 때 절단되는 막대기의 수이다.

여는 괄호가 들어오면 stack에 push 한다.

닫는 괄호가 들어오면 다음과 같이 판단한다.

닫는 괄호 이전의 괄호가 여는 괄호였다면 pop을 하고 나서 정답에 +stack.size()를 해준다.

닫는 괄호 이전의 괄호가 여는 괄호가 아니라면 pop을 하고나서 정답에 +1을 해준다.

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
	string s;
	cin >> s;

	stack<char> st;
	int cnt = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(')
			st.push(s[i]);
		else
		{
			if (s[i - 1] == '(')
			{
				st.pop();
				cnt += st.size();
			}
			else
			{
				st.pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}

풀이

문제부터 이해해보자.

핵심은 스택을 이용해서 원하는 숫자를 만들 수 있는지? 아닌지이다.

하나씩 차근차근 진행해보면,

4를 만들기 위해서는 push 4번, pop 1번

+ + + + Stack [1, 2, 3, 4]

+ + + + - Stack [1, 2, 3]

3을 만들기 위해서는 pop 1번

+ + + + - - Stack [1, 2]

6을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + Stack [1, 2, 5, 6]

+ + + + - - + + - Stack [1, 2, 5]

8을 만들기 위해서는 push 2번, pop 1번

+ + + + - - + + - + + Stack [1, 2, 5, 7, 8]

+ + + + - - + + - + + - Stack [1, 2, 5, 7]

7을 만들기 위해서는 pop 1번

+ + + + - - + + - + + - - Stack [1, 2, 5]

5, 2, 1을 각 각 pop 1번씩만 해주면 해결할 수 있다.

따라서 결과는

+ + + + - - + + - + + - - - - -

구현은

queue에 현재 만들고자 하는 숫자들을 넣어주고,

현재 만들려고 하는 숫자를 stack의 top과 비교하면서 만들 수 있다면 push 하면서 +를 채워나가고

만들지 못한다면 No를 출력하면 된다.

여기서 만들지 못한다는 것은 현재 queue의 front 값과 stack의 top 부분에서

queue.front() < stack.top() 이면 만들지 못하는 것이다.

ret이라는 벡터는 출력을 위한 +, -를 저장하는 공간이다.

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

int n;
stack<int> st;
queue<int> q;
vector<char> ret;
// stack에 push하는 순서는 반드시 오름차순
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		q.push(x);
	}

	int num = 1;
	bool ok = true;
	while (!q.empty())
	{
		int now = q.front();

		if (!st.empty() && st.top() > now)
		{
			ok = false;
			break;
		}
		if (st.empty())
		{
			st.push(num++);
			ret.push_back('+');
		}
		else
		{
			if (st.top() == now)
			{
				st.pop();
				ret.push_back('-');
				q.pop();
			}
			else
			{
				st.push(num++);
				ret.push_back('+');
			}
		}
	}

	if (ok)
	{
		for (int i = 0; i < ret.size(); i++)
			cout << ret[i] << '\n';
	}
	else
		cout << "NO\n";

	return 0;
}

풀이

맵에서 울타리 '#'가 아닌 지역을 시작점으로 탐색을 해서 양과 늑대의 수를 체크한다.

이때 양의 수가 늑대의 수보다 많다면 양이 싸움에서 이기는 것이고,

양의 수가 늑대의 수보다 작거나 같다면 양이 싸움에서 지는 것으로 구현하면 된다.

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

int r, c, wolf, sheep;
char field[251][251];
bool vis[251][251];

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

void findSheepAndWolf(int x, int y)
{
	int w = 0, s = 0;
	queue<pair<int, int >> q;
	q.push({ x,y });
	vis[x][y] = true;
	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (field[x][y] == 'v') w++;
		if (field[x][y] == 'k') s++;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
			if (field[nx][ny] != '#' && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ nx,ny });
			}
		}
	}

	if (s > w) 
		sheep += s;
	else 
		wolf += w;
}

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

	cin >> r >> c;
	for (int i = 0; i < r; ++i)
		for (int j = 0; j < c; ++j)
			cin >> field[i][j];

	for (int i = 0; i < r; ++i)
	{
		for (int j = 0; j < c; ++j)
		{
			if (field[i][j] != '#' && !vis[i][j])
			{
				findSheepAndWolf(i, j);
			}
		}
	}

	cout << sheep << ' ' << wolf << '\n';
	return 0;
}

풀이

N X M 크기의 맵에서 (1,1)에서 출발해서 (N,M)까지 도달하는데 걸리는 최소의 칸 수를 구하는 문제이다.

칸 과 칸 사이는 1이라는 비용으로 생각할 수 있다.

(1,1) -> (1,2) 로 가는 비용이 1이라는 뜻이다. 만약에 비용이 달랐다면 다른 방법으로 풀어야 한다.

비용이 모두 1로 같기 때문에 이 문제는 BFS 알고리즘으로 해결할 수 있다.

여기서는 (0,0) -> (N-1, M-1)로 구현했다.

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

int n, m;
int board[101][101];
bool vis[101][101];

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

	queue<pair<pair<int, int>, int> > q;
	q.push({ {0,0}, 1 });
	vis[0][0] = true;
	while (!q.empty())
	{
		int x = q.front().first.first;
		int y = q.front().first.second;
		int cnt = q.front().second;
		q.pop();

		if (x == n - 1 && y == m - 1)
			return cnt;

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
			if (board[nx][ny] == 1 && !vis[nx][ny])
			{
				vis[nx][ny] = true;
				q.push({ {nx,ny}, cnt + 1 });
			}
		}
	}

	return -1;
}

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

	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		string str;
		cin >> str;
		for (int j = 0; j < str.length(); ++j)
		{
			board[i][j] = str[j] - '0';
		}
	}

	cout << bfs() << '\n';
	return 0;
}

풀이

컴퓨터를 어떻게 코드 상으로 연결할지 생각하자.

이 문제에서는 주어진 간선만 표현하면 되므로 인접 리스트가 편하다.

이때 주의할 점은 양방향 간선으로 그래프를 표현해야 한다.

바이러스의 전파는 무조건 컴퓨터 1번으로부터 시작하므로 1번부터 인접한 컴퓨터를 카운트하면서 진행하면 된다.

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

int v, e;
vector<int> computer[101];
bool vis[101];

int bfs()
{
	int cnt = 0;
	queue<int> q;
	q.push(1);
	vis[1] = true;
	while (!q.empty())
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < computer[now].size(); ++i)
		{
			int next = computer[now][i];
			if (!vis[next])
			{
				cnt++;
				vis[next] = true;
				q.push(next);
			}
		}
	}

	return cnt;
}

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

	cin >> v >> e;
	for (int i = 0; i < e; ++i)
	{
		int a, b;
		cin >> a >> b;
		computer[a].push_back(b);
		computer[b].push_back(a);
	}

	cout << bfs() << '\n';
	return 0;
}