[백준 / BOJ] 14725 개미굴

문제

출처 : www.acmicpc.net/problem/14725

14725번: 개미굴

로봇 개미가 개미굴 입구에서 각 층을따라 내려오며 먹이를 탐색한다.

이때 로봇 개미 발견한 먹이를 순서대로 알고있을때,

개미굴의 구조를 출력하는 문제다.

 

풀이

처음에는 기본적인 그래프 탐색으로 풀수있겠다 생각했는데, 시간초과가 난다.

Trie를 사용안하면, 자신과 연결된 개미굴이 자신이 찾고있는 개미굴인지 매 탐색마다 확인해야하므로 15번 반복하고, 문자의 갯수는 총 15000개가 있으므로, 15^15000번 반복해야한다.

 

Trie자료구조을 이용해 풀어야하는 문제였다.

 

더이상 아래 더보기 방법으로는 풀수없다.

더 이상 아래 방법으로는 풀수없다.

- 문자열의 한 글자 한 글자 마다 구조체를 만들어서 문자열을 늘려간다. (BANANA = B - A - N - A - N - A)

- 이때, 저장할 위치에 이미 해당 문자가 있다면 더 이상 늘리지 않고 idx만 증가시켜준다.

- 저장할 글자가 문자열의 끝이라면, 해당 위치가 한 문자열의 끝임을 표시해준다. (BANANA = B - A - N - A - N - A(끝 표시))

- 문자열의 길이보다 더 작은 위치에서 구조체 탐색이 끝났다면, 끝난지점부터 탐색하지 못한 문자열을 뒤에 이어준다.

(BANANA BANANA = B - A - N - A - N - A(끝 표시) - B - A - N - A - N - A(끝 표시))

(BANANA BANANANA = B - A - N - A - N - A(끝 표시) - B - A - N - A - N - A(끝 표시) - N - A(끝 표시))

 

예를들어, 

 

2

2 BB AA

3 BB AA AB

이런 형태의 입력이 주어졌다면,

(! 는 한 문자열의 끝지점 표시) (파란색 글자는 새로 추가된 문자열)

B - B(!) - A - A(!)

B - B(!) - A - A(!) - A - B(!)

위 와 같은 형태로 저장해놓고, 출발점에서 탐색을 하며 문자열의 끝지점에 도착했다면 출력해주면 된다.

 

이런식으로 코드를짜면, 총 문자열의 길이는 15*15000 이 되고, 탐색또한 문자열의 길이만큼 탐색하므로 15*15000 이 되서 시간초과를 피할수있다.

 

맞긴 했는데, 반례가 존재한다. 

입력 :

2

2 A ABC

2 A A

----------

옳은 출력 : 

A

--A

--ABC

---------

내 출력 :

A

--ABC

 

exist함수 구현방식을 바꾸면 어찌 반례를 피할수있을거 같긴한데(로직 자체가 틀렸나..?), 내 코드에선 ABC가 먼저 입력되고 같은 부모 개미굴의 자식으로 A가 입력되면 ABC에 의해서 A가 무시되고 있는것 같다.

 

반례 테스트케이스는 아래에 추가적으로 적어놨다.

반례 설명 게시글 : www.acmicpc.net/board/view/61861

글 읽기 - 데이터를 추가해주세요

 

Trie구조에 map을 이용해서 풀은 문제다.

기존 Trie구조는 한글자 한글자씩 끊어서 저장해 문자를 빠르게 탐색하지만, 이 문제에서는 한글자 단위가 아닌, 한문장 단위로 저장해놓고 탐색해야한다. 

예제 1

3

2 B A

4 A B C D

2 A C

일때, 저장 되는 구조를 만들어보면

 

1. 우선 첫 입력(2 B A)에서 다음과 같이 만들어진다.

입구 

B

--A

 

2. 두번때 입력(4 A B C D)도 마찬가지로 다음과 같이 만들어진다.

입구 

B

--A

A

--B

----C

------D

 

3. 세번째 입력(2 A C)가 만들어지는 과정이 중요한데,

입구에서 A를 만들려할때, 이미 A가 존재한다. 따라서 A는 만들지않고, 주솟값만 A로 바꾼다. 다음 C를 만들려할때, C가 존재하는지 확인한다. 이때 존재하지않으므로 C를 만들어서 붙인다.

 

따라서 최종 구조는

입구 

B

--A

A

--B

----C

------D

--C

가 된다.

 

위 과정을 정리하면,

1. 현재 개미굴의 자식굴에 입력할려는 문자열이 존재하는지 확인한다.

2. 존재한다면 굴을 더 만들지않고, 주솟값만 해당 자식으로 바꾼다.

3. 존재하지않는다면, 굴을 하나 더 만들어서 해당 굴에 입력값을 넣는다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/14725%20%EA%B0%9C%EB%AF%B8%EA%B5%B4/main2.cpp

devxb/JJUNalgo