CodeDrive

문제:

보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 이동은 상하좌우로 이웃한 육지로만 가능하며, 한 칸 이동하는데 한 시간이 걸린다. 보물은 서로 간에 최단 거리로 이동하는데 있어 가장 긴 시간이 걸리는 육지 두 곳에 나뉘어 묻혀있다. 육지를 나타내는 두 곳 사이를 최단 거리로 이동하려면 같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다.

예를 들어 위와 같이 지도가 주어졌다면 보물은 아래 표시된 두 곳에 묻혀 있게 되고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간이 된다.

보물 지도가 주어질 때, 보물이 묻혀 있는 두 곳 간의 최단 거리로 이동하는 시간을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다.

출력:

첫째 줄에 보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력한다.

풀이방법:

for(bfs) 방법을 사용해야 하는 방법으로 시간이 많이 필요한 문제라 생각했고, pypy3으로 통과했다. 지도의 모든 L에 대해서 bfs를 수행한다. 각 bfs에서는 해당 L로부터 가장 멀리 갈 수 있는 거리를 찾는다.

문제링크:

https://www.acmicpc.net/problem/2589

문제:

남극에 사는 김지민 선생님은 학생들이 되도록이면 많은 단어를 읽을 수 있도록 하려고 한다. 그러나 지구온난화로 인해 얼음이 녹아서 곧 학교가 무너지기 때문에, 김지민은 K개의 글자를 가르칠 시간 밖에 없다. 김지민이 가르치고 난 후에는, 학생들은 그 K개의 글자로만 이루어진 단어만을 읽을 수 있다. 김지민은 어떤 K개의 글자를 가르쳐야 학생들이 읽을 수 있는 단어의 개수가 최대가 되는지 고민에 빠졌다.

남극언어의 모든 단어는 "anta"로 시작되고, "tica"로 끝난다. 남극언어에 단어는 N개 밖에 없다고 가정한다. 학생들이 읽을 수 있는 단어의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다.

출력:

첫째 줄에 김지민이 K개의 글자를 가르칠 때, 학생들이 읽을 수 있는 단어 개수의 최댓값을 출력한다.

풀이방법:

 일반적인 브루트포스 방법을 사용하면 시간초과가 날 수 있기 때문에, 비트마스킹이라는 방법을 사용했다. "anta", "tica"에서 사용되는 "a","n","t","i","c"를 제외하고 나머지 알파벳에 대해서 20개의 비트가 있다고 가정하고, 사용하면 1을 올리고, 사용하지 않으면 0으로 냅두는 방법을 사용한다. 

 항상 5개의 알파벳은 사용해야 하기 때문에, k가 5보다 작으면 읽을 수 있는 단어가 없다. 이외의 경우에는 가능한 알파벳에서 k-5개의 알파벳을 뽑은 뒤(가능한 모든 조합에 대해), 비트마스킹을 통해 갯수를 세고, 그 중 최댓값을 반환하도록 한다.

문제링크:

https://www.acmicpc.net/problem/1062

문제:

창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다.

키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다.

강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이스를 입력했다면, '-'가 주어진다. 이때 커서의 바로 앞에 글자가 존재한다면, 그 글자를 지운다. 화살표의 입력은 '<'와 '>'로 주어진다. 이때는 커서의 위치를 움직일 수 있다면, 왼쪽 또는 오른쪽으로 1만큼 움직인다. 나머지 문자는 비밀번호의 일부이다. 물론, 나중에 백스페이스를 통해서 지울 수는 있다. 만약 커서의 위치가 줄의 마지막이 아니라면, 커서 및 커서 오른쪽에 있는 모든 문자는 오른쪽으로 한 칸 이동한다.

출력:

각 테스트 케이스에 대해서, 강산이의 비밀번호를 출력한다. 비밀번호의 길이는 항상 0보다 크다.

풀이방법:

 두 개의 스택을 이용해서 "<",  ">", "-"와 같은 특수 문자들을 해결하도록 한다. 

우선 일반적으로는 stack에다가 들어온 값을 저장한다. 그러다가 "<"를 만난다면 왼쪽으로 커서를 이동해야 하므로, stack의 값을 빼서, stack2에 담고, 반대로 ">"를 만난다면 stack2의 값을 빼서 stack에 담도록 한다. "-"는 stack의 값을 제거하면 된다.

 마지막으로 stack2의 값이 남아 있을 수도 있기 때문에, 이 값을 뒤집어 stack과 이어붙이도록 한다.

문제링크:

https://www.acmicpc.net/problem/5397

문제:

상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.

상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 20 이하이어야 한다. 예를 들어, "8+3+2-4-8-7+2+4+0+8=8"은 올바른 등식이지만, 8+3+2-4-8-7이 음수이기 때문에, 상근이가 만들 수 없는 등식이다.

숫자가 주어졌을 때, 상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 숫자의 개수 N이 주어진다. (3 ≤ N ≤ 100) 둘째 줄에는 0 이상 9 이하의 정수 N개가 공백으로 구분해 주어진다.

출력:

첫째 줄에 상근이가 만들 수 있는 올바른 등식의 개수를 출력한다. 이 값은 263-1 이하이다.

풀이방법:

 앞에서 부터 덧셈, 뺄셈을 수행하면서 0이나 20을 넘어가는 수가 발생하면 저장을 하지 않는 DP 방식으로 풀면 된다. 0~20의 배열을 생성한 뒤에 한 step이 지나갈 때마다 덧셈, 뺄셈을 한 수를 집어 넣는다. 그림으로 보면 다음과 같다.

1) 첫 행은 첫 값을 이용해 다음과 같이 초기화 한다.

2) 다음 행은 이전 행의 1 값에 대해서 덧셈과 뺄셈을 반복한다.

3) 0과 20을 넘어가는 숫자가 있다면 제외한다.

2)와 3) 과정을 반복하고, dp[n-2][numbers[n-1]]을 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5557

문제:

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력:

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

풀이방법:

https://codedrive.tistory.com/386 다음 수열과 비슷한 문제다.

다음 순열에서 했던 내용과 달리 이전 수열에서는 정반대로만 수행하면 문제를 해결할 수 있다.

문제링크:

https://www.acmicpc.net/problem/10973

문제:

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

• 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
• 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
• 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
• 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
• 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (0 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력:

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

풀이방법:

**이 문제는 pypy3으로 통과했습니다.**

 이 문제는 for(bfs)라고 생각했다. 우선 bfs를 사용한 이유는 한 나라로부터 인접한 국가들을 찾는 방법은 bfs가 가장 적당하다고 생각했기 때문이다. 하지만 이러한 bfs를 NxN 크기의 땅에 모두에 대해서 수행해야 했기 때문에 for(bfs)라고 생각했다. 그리고 이러한 문제때문에 시간초과가 발생할 수 있을 것 같다는 걱정이 들었는데, 실제로 python3으로는 시간초과가 발생하여서 pypy3으로 이 문제를 해결하였다.

 bfs를 통해서 국경이 열리는 나라들을 찾으며 인구 수를 더하며 count를 센다. 한 번의 bfs 탐색이 끝나게 되면, 업데이트를 하는 과정을 거치고, 다시 이어서 bfs를 수행하도록 한다. 

 이러한 과정을 인구 이동이 발생하지 않을 때까지 반복한다.

문제링크:

https://www.acmicpc.net/problem/16234

문제:

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력:

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

풀이방법:

주어진 조건대로 톱니바퀴가 동작하는 알고리즘을 구현하면 되는 문제다.

 회전하는 것을 구현하기 위해서 collections에 있는 deque의 rotation 함수를 사용한다. 따라서 입력을 받을 때, 각 톱니바퀴들은 deque의 자료형을 가지게 된다.

 입력으로 주어지는 톱니바퀴를 우선적으로 회전시킨 후에 조건에 맞는다면 주변 톱니바퀴도 회전시킨다. 12시 방향이 모든 배열의 시작이기 때문에, 톱니바퀴들이 서로 만나는 인덱스는 '2'번 인덱스와 '-2'번 인덱스다. 따라서 두 인덱스가 다르고, 아직 방문하지 않은 톱니바퀴라면 현재 톱니바퀴의 반대 방향으로 회전시키도록 한다.

문제링크:

https://www.acmicpc.net/problem/14891

문제:

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력:

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

풀이방법:

 nodes라는 이중배열을 사용해서 입력으로 주어지는 연결된 두 정점 사이의 관계를 기록한다. 그리고 항상 트리의 루트는 1이라고 정해졌기 때문에, 1부터 dfs를 사용해서 노드들을 탐색하면서 parent를 기록한다.

문제링크:

https://www.acmicpc.net/problem/11725

문제:

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력:

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

풀이방법:

이 문제는 다른 방법을 사용하면 쉽게 풀 수 있겠지만, 트라이 자료구조를 활용해서 풀어보았다. 생각보다 시간제한이 어려웠던 문제라서 최대한 시간을 줄이고자, Node를 정의해서 풀었던 다른 문제들과는 달리 하나의 class만으로 해결해보도록 구성해보았다.

class Trie(object):
    @classmethod
    def __init__(self):
        self.root = {}
        self.terminate = 'eof'
        
    @classmethod
    def insert(self, string):
        currNode = self.root
        for chr_ in string:
            if chr_ not in currNode:
                currNode[chr_] = {}
            currNode = currNode[chr_]
        currNode[self.terminate] = string
        
    @classmethod
    def search(self,string):
        currNode = self.root
        for chr_ in string:
            if chr_ in currNode:
                currNode = currNode[chr_]
            else:
                return False
        if 'eof' in currNode.keys():
            return True
        else:
            return False

n, m = map(int,input().split())
T = Trie()
for _ in range(n):
    T.insert(input())
answer = 0
for _ in range(m):
    if T.search(input()):
        answer+=1
        
print(answer)

문제링크:

https://www.acmicpc.net/problem/14425

문제:

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠)  일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• 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) 이다. 

출력:

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

풀이방법:

문자열 알고리즘 중 효율성이 가장 좋은 트라이(Trie) 알고리즘을 사용해서 입력받는 문자열을 정리하고, 별도의 탐색없이 지정된 출력형식으로 출력하면 되기 때문에, 재귀를 사용해서 문제에서 요구하는 방식대로 출력하도록 한다.

class Node(object):
    def __init__(self,name,flag=False):
        self.parent = name
        self.terminate = flag
        self.child = {}
        
    def __str__(self):
        return self.parent
        
class Trie(object):
    @classmethod
    def __init__(self):
        self.root = Node(None)
        
    @classmethod
    def insert(self, food):
        currNode = self.root
        for f in food:
            if f not in currNode.child:
                currNode.child[f] = Node(f)
            currNode.terminate = False
            currNode = currNode.child[f]
        currNode.terminate = True
        
    @staticmethod
    def antPrint(curNode,count):
        currList = sorted(list(curNode.child))
        for curr in currList:
            print("-"*count*2,end='')
            print(curNode.child[curr])
            Trie.antPrint(curNode.child[curr],count+1)

n = int(input())
T = Trie()
for _ in range(n):
    list_ = input().split()
    m, foods = list_[0], list_[1:]
    Trie.insert(foods)
Trie.antPrint(Trie.root,0)

문제링크:

https://www.acmicpc.net/problem/14725