[ BOJ 오답노트 ] 5107 C++ : 마니또

해결이 어려웠던 이유는 

1. giver와 receiver가 쌍으로 존재하는데 이걸 어떤 자료구조를 써야 하는지 판단이 어려웠다.

2. BFS를 사용해야 할 것 같은데 Queue가 빈 상태가 되었다고 하나의 테스트 케이스가 끝난 것이 아니라서 어떻게 처리해야 할 지 어려웠다.

 

 

1. 문제 1번 : 'unordered_map'

출처 : https://www.geeksforgeeks.org/unordered_map-in-cpp-stl/

(1) map보다 더 빠른 탐색이 가능한 자료구조이다.

map은 탐색에서 Binary Search Tree를 사용하여 O(log n)이라면, unordered_map은 Hash Table을 사용하여 O(1)이다.

 

(2) 중복된 데이터를 허용하지 않는다.

map에 비해서 데이터가 많을 때 월등히 좋은 성능을 보인다.

 

(3) iterator로 접근해야 한다.

index로 접근 불가능하다. 시작은 begin(), 끝은 end()로 접근하여 for문으로 하나씩 접근 가능하다.

# include <unordered_map>
using namespace std;

unordered_map<int, int> um;

for (auto it = um.begin(); it != um.end(); it++) {
	cout << it->first << " / " << it->second;
}

 

(4) 메서드

- empty() : unordered_map이 비었는지 확인.

- size() : unordered_map의 크기를 확인

- operator '[ key ]' : key를 통해서 value를 지정하는 operator

- find(key) : key에 해당하는 원소 찾기

- begin() : unordered_map의 시작

- end() :  unordered_map의 끝

 

 

 

2. 문제 2번 : 이중 for문을 사용한다.

설명이 힘드니까 코드로 보면,

for (auto it = visited.begin(); it != visited.end(); ++it) {
    if (it->second == true) continue;

    visited[it->first] = true;
    Q.push(it->first);

    while (!Q.empty()) {
        string cur = Q.front(); Q.pop();
        for (auto itt = visited.begin(); itt != visited.end(); ++itt) {
            if (itt->second == true || manitto[cur] != itt->first) continue;
            Q.push(itt->first);
            visited[itt->first] = true;
        }
    }
    count++;
}

방문 여부를 저장한 unordered_map (visited)와 giver와 receiver의 관계를 저장한 unordered_map (manitto)를 선언한다.

이중 for문으로 반복하게 해서 이미 방문한 원소는 continue로 벗어나게 했고, Queue로 BFS를 구현해서 주고 받는 관계를 따라가도록 했다.

 

 

 

3. 전체 코드

# include <bits/stdc++.h>
# include <unordered_map>
using namespace std;

int n, test_case = 0;
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	while (true) {
		cin >> n;
		if (n == 0) break;

		unordered_map<string, string> manitto;
		unordered_map<string, bool> visited;
		test_case++;

		string p1, p2;
		for (int i = 0; i < n; i++) {
			cin >> p1 >> p2;
			manitto[p1] = p2;
			visited[p1] = false;
			visited[p2] = false;
		}
		
		int count = 0;
		queue<string> Q;
		
		for (auto it = visited.begin(); it != visited.end(); ++it) {
			if (it->second == true) continue;

			visited[it->first] = true;
			Q.push(it->first);

			while (!Q.empty()) {
				string cur = Q.front(); Q.pop();
				for (auto itt = visited.begin(); itt != visited.end(); ++itt) {
					if (itt->second == true || manitto[cur] != itt->first) continue;
					Q.push(itt->first);
					visited[itt->first] = true;
				}
			}
			count++;
		}
		cout << test_case << " " << count <<"\n";
	}
}

 

 

푸는데 꽤 오랜 시간이 걸려서 오답 노트를 작성했다...

아직 한참 멀었군아...