문제 : 개미굴
문제
개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네.
개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.
한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!
우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.
행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.
로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.
이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.
로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)
다음은 로봇 개미들이 윤수에게 보내준 정보다.
KIWI BANANA
KIWI APPLE
APPLE APPLE
APPLE BANANA KIWI
(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)
윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.
APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA
(개미굴의 각 층은 "--" 로 구분을 하였다.
또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)
우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.
한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!
행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.
입력
첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000)
두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)
다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다.
3
2 B A
4 A B C D
2 A C
출력
개미굴의 시각화된 구조를 출력하여라.
개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.
A
--B
----C
------D
--C
B
--A
문제 풀이
물론 조건 코딩으로 이용해서 판별할 수도 있다. 이 문제가 쉽다고 할 수 있는 이유 중에는 하나는 왼쪽 오른쪽 노드를 구별하지 않고, 왼쪽부터 라는 무조건적 조건이 있기때문이고 개미는 노드를 끝까지 방문하기 때문에 조건을 통해 구별 지을 수 있지만, 내가 원하는 풀이는 아니다.
왼쪽 노드부터 insert 해주는게 내가 원하는 풀이임을 나는 알고 있다...
혼자 쩔쩔매다가 다른분의 풀이를 참고했다. 아주 깔끔하게 푸신거 같다.(출처 : https://ansohxxn.github.io/algorithm/trie/)
class AntTree
{
private:
std::map<std::string, AntTree*> Child;
public:
void Insert(std::vector<std::string> vector, int index);
void Output(int depth);
};
void AntTree::Insert(std::vector<std::string> foods, int index)
{
if (foods.size() <= index)
{
return;
}
if (Child.find(foods[index]) == Child.end())
{
Child[foods[index]] = new AntTree();
}
Child[foods[index]]->Insert(foods, index + 1);
}
void AntTree::Output(int depth)
{
for (auto const& ch : Child)
{
for (int j = 0; j < depth; j++)
{
std::cout << "--";
}
std::cout << ch.first << std::endl;
ch.second->Output(depth + 1);
}
}클래스를 구현하여 풀이하셨다. 풀이 방법은 AntTree Root 객체를 선언하고, MAP에 Find 함수를 이용하여 MAP Find에서 값이 존재하지 않으면 재귀 형태를 통해 Insert 하는 방법이다.
방법론 적으로 중요한 것은
Child[foods[index]] = new AntTree();
Key 값으로 Foods[Index] 값을 넣어주고 , Second 값에 객체를 생성해서 넘겨주는 방법이다. 이게 낯설게 보였다. 가만보니 MAP에 대한 이해가 부족했던거 같다..
int main()
{
std::cin >> n;
AntTree *root = new AntTree();
for (int i = 0; i < n; i++)
{
int k;
std::cin >> k;
std::vector<std::string> foods(k);
for (int j = 0; j < k; j++)
{
std::cin >> foods[j];
}
root->Insert(foods, 0);
}
root->Output(0);
}메인 함수에서는 마찬가지로 Foods 배열에 첫번째 음식들을 넣어주고 그 값들을 매번 Insert 해 준다.
이렇게 class 형태의 문제들을 많이 풀어보면 좋을거 같다는 생각이 들었다. 이런 문제형태는 트리 탐색이나 Make Tree 하는 문제에 많으니, 앞으로 백준에서 골라서 풀어봐야겠다.
전체 코드
#include <iostream>
#include <map>
#include <vector>
#include <string>
int n;
class AntTree
{
private:
std::map<std::string, AntTree*> Child;
public:
void Insert(std::vector<std::string> vector, int index);
void Output(int depth);
};
void AntTree::Insert(std::vector<std::string> foods, int index)
{
if (foods.size() <= index)
{
return;
}
if (Child.find(foods[index]) == Child.end())
{
Child[foods[index]] = new AntTree();
}
Child[foods[index]]->Insert(foods, index + 1);
}
void AntTree::Output(int depth)
{
for (auto const& ch : Child)
{
for (int j = 0; j < depth; j++)
{
std::cout << "--";
}
std::cout << ch.first << std::endl;
ch.second->Output(depth + 1);
}
}
int main()
{
std::cin >> n;
AntTree *root = new AntTree();
for (int i = 0; i < n; i++)
{
int k;
std::cin >> k;
std::vector<std::string> foods(k);
for (int j = 0; j < k; j++)
{
std::cin >> foods[j];
}
root->Insert(foods, 0);
}
root->Output(0);
}