[BOJ 17839] Baba is Rabbit

서론

사랑하는 나의 모교 UNIST에서 개최한 첫 알고리즘 대회의 문제다. 나는 2회 대회에 참가했는데, 알고리즘 준비가 전혀 안되어 있던 상태였기 때문에 허겁지겁 1회 대회 문제를 풀어보았던 기억이 있는데... 그 때는 이 문제조차 어렵게 느껴졌는데 2달 정도 공부하고 나서는 편하게 느껴졌다.

전형적인 solved.ac 실버 수준의 그래프 탐색 문제로, 이 문제를 잘 풀수 있다면 대다수의 실버 그래프 탐색 문제는 풀 수가 있을 것이다.

17839번: Baba is Rabbit

 

문제

원이는 요즘 유행하는 게임을 하고 있다. 이 게임은 is 라는 단어를 이용해 어떤 사물을 다른 사물로 바꿀 수 있다. 규칙은 다음과 같다. 컴공 친구들은 이렇게 유행에 뒤떨어지지 않는데... 너드만의 전공이던 시절은 한 물 갔다.

• 게임 시작 시 몇 개의 명령을 설정해놓는다.
  • 이 때, 모든 명령의 형태는 p is q 의 형태이며, p, q는 사물이다.
• 두 사물 p, q에 대해 p is q 라는 명령은 사물 p를 사물 q로 바꾼다.
  • 이러한 행위를 명령을 적용한다고 부른다.

어떤 사물 p에 대해 적용할 수 있는 명령이 두 가지 이상이면, 그 중 아무거나 하나 골라서 적용할 수 있다. (아무 명령도 적용하지 않을 수도 있다.) 그리고 어떤 사물 p에 명령을 한 번 이상 적용한 결과로 다시 p가 나오는 경우는 없다.

게임 초기에 설정된 명령들이 주어졌을 때, Baba에 명령을 적용하여 어떤 사물로 만들 수 있는지 구해보자.

입력

첫 줄에 전체 명령의 수 N(1 ≤ N ≤ 100,000)이 주어진다.

이후 N개의 줄에 걸쳐 명령이 주어진다. 각 명령은 p is q의 형태로 주어지며,  p와 q는 첫 글자가 영문 대문자이고, 나머지 글자는 영문 소문자인 길이 10 이내의 문자열이다.

출력

Baba에 명령을 한 번 이상 적용한 결과로 나올 수 있는 사물을 사전순으로 출력한다. 단, 적용할 수 있는 명령이 없다면, 아무것도 출력하지 않는다.

 

이 문제를 전형적인 그래프 문제로 바꿔본다면, baba 정점에서 연결된 모든 정점의 이름을 방문하면서 중복되지 않도록 사전 순으로 출력하는 문제가 될 것이다. 이 문제의 경우에는 DFS와 BFS가 영향을 끼치지 않으므로, 취향껏 풀면 된다.

 

그래프는 어떻게 만들까?

올해 취준을 위해 처음 알고리즘 공부를 시작할 때 접했던 그래프 문제는 공포 그 자체였다. 순서도 섞여있는 30만 개의 정점들을 포함한 그래프는 어떻게 만들어야 하나 하는 막막함부터 앞섰다.

이번 문제 역시 N이 10만 개에 육박하기 때문에 100000*100000 사이즈의 2차원 배열을 만드는 건 불가능하고, (한 정점에서 다수의 정점으로 여러 개의 엣지가 연결되어 있을수도 있는 문제기도 했다) 데이터 구조에서 배웠던 LinkedList 기반의 그래프를 만들어야 하나? 하는 생각에 알고리즘은 쉽지 않다고 생각을 했었지만...

 

그래프 탐색 문제 대부분은 HashMap을 이용해 구현할 수 있다.

key값이 출발점이라면, value값은 도착점이 될 것이다. 양방향 엣지라면 key value 순서를 바꿔서 HashMap에 put해주면 된다. 만약 한 정점에서 여러 정점으로 뻗어나갈 수 있는 경우, value는 단일 정수가 아니라 선형 자료구조로 정해주면 충분하다. HashMap에서 주의할 점은, 처음 입력을 받아 HashMap에 입력할 때 입력으로 들어온 key를 HashMap이 가지고 있지 않다면, 어떠한 형태의 list든 인스턴스를 만들어 넣어주어야 한다.

 

코드

아래 코드는 DFS 탐색을 통해 그래프 전체를 순회하며, 재귀를 사용하지 않고 stack을 이용하여 구현하였다.

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int N = Integer.parseInt(br.readLine());
		HashMap<String, LinkedList<String>> hm = new HashMap<>();
		PriorityQueue<String> pq = new PriorityQueue<>();
		for(int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String src = st.nextToken();
			st.nextToken();
			String dest = st.nextToken();
			if(!hm.containsKey(src)) {
				hm.put(src, new LinkedList<>());
			}
			hm.get(src).offer(dest);
		}
		Stack<String> stk = new Stack<>();
		stk.push("Baba");
		StringBuilder sb = new StringBuilder();
		while(!stk.isEmpty()) {
			String curr = stk.pop();
			if(!hm.containsKey(curr))break;
			LinkedList<String> next = hm.get(curr);
			while(!next.isEmpty()) {
				String s = next.poll();
				stk.push(s);
				pq.offer(s);
			}
		}
		String prev = "";
		while(!pq.isEmpty()) {
			String curr = pq.poll();
			if(!prev.equals(curr)) {
				sb.append(curr+"\n");
			}
			prev = curr;
		}
		bw.write(sb.toString());
		bw.flush();
		br.close();
		bw.close();
	}

}

 

문제의 의의

무난한 그래프 탐색 문제입니다. 실버 수준의 그래프 탐색 문제는 그래프를 제대로 구현하고 탐색하는 법을 알기만 한다면 큰 문제없이 풀 수 있습니다. 기본에 충실한 문제이기에 풀어보기를 권장합니다.