[BOJ] 백준 9177번 단어 섞기 (Java)

#9177 단어 섞기

난이도 : 골드 4

유형 : 문자열 / bfs

9177번: 단어 섞기

▸ 문제

세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : tcraete

보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째 단어를 만들 수 있다. 아래와 같이 두 번째 예를 들어보자.

• 첫 번째 단어 : cat
• 두 번째 단어 : tree
• 세 번째 단어 : catrtee

이 경우 역시 가능하다. 그렇다면 "cat"과 "tree"로 "cttaree"를 형성하는건 불가능하다는걸 눈치챘을 것이다.

▸ 입력

입력의 첫 번째 줄에는 1부터 1000까지의 양의 정수 하나가 주어지며 데이터 집합의 개수를 뜻한다. 각 데이터집합의 처리과정은 동일하다고 하자. 각 데이터집합에 대해, 세 개의 단어로 이루어져 있으며 공백으로 구분된다. 모든 단어는 대문자 또는 소문자로만 구성되어 있다. 세 번째 단어의 길이는 항상 첫 번째 단어와 두 번째 단어의 길이의 합이며 첫 번째 단어와 두 번째 단어의 길이는 1~200이다.

▸ 출력

각 데이터집합에 대해 다음과 같이 출력하라.

만약 첫 번째 단어와 두 번째 단어로 세 번째 단어를 형성할 수 있다면

Data set n: yes

과 같이 출력하고 만약 아니라면

Data set n: no

과 같이 출력하라. 물론 n은 데이터집합의 순번으로 바뀌어야 한다. 아래의 예제 출력을 참고하라.

 

문제 풀이  

두 단어는 마음대로 섞어도 되지만 각 단어 자체에서는 순서를 지켜줘야 한다. 그래서 탐색할 때 두 가지의 경로로 나뉜다.

1. 첫 번째 단어 맨 앞 글자와 일치하는 경우
2. 두 번째 단어 맨 앞 글자와 일치하는 경우

 

이 두 경우를 모두 고려해서 탐색을 해주면 된다. DFS 백트래킹을 사용하면 최악의 경우 2번씩 계속 분기한다하면 시간초과가 발생한다. 그래서 BFS을 통해 최단거리 탐색을 해줘야 한다. 첫 번째 단어와 두 번째 단어를 (x, y)로 생각하고 세 번째 단어와 일치하는 경로를 차례대로 밞아 나가는 경로를 구해준다고 생각하면 편하다.

 

 

 

풀이 코드 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static char[] c1,c2, out;
	static boolean[][] check;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringBuilder sb = new StringBuilder();
		int idx = 0;
		while(idx++ < n) {
			String[] str = br.readLine().split(" ");
			c1 = str[0].toCharArray();
			c2 = str[1].toCharArray();
			out = str[2].toCharArray();
			if(bfs()) {
				sb.append("Data set " + idx+": yes\n");
			}else {
				sb.append("Data set " + idx+": no\n");
			}
		}
		System.out.println(sb.toString());
	}
	
	static boolean bfs() {
		Queue<int[]> q = new LinkedList<>();
		check = new boolean[201][201];
		q.add(new int[] {0,0,0});
		check[0][0] = true;
		
		while(!q.isEmpty()) {
			int idx1 = q.peek()[0];
			int idx2 = q.peek()[1];
			int outIdx = q.peek()[2];
			q.poll();
			
			if(outIdx == out.length) {
				return true;
			}
			
			if(idx1<c1.length && !check[idx1+1][idx2] && 
					c1[idx1] == out[outIdx]) {
				q.add(new int[] {idx1+1, idx2, outIdx+1});
				check[idx1+1][idx2] = true;
			}
			
			if(idx2<c2.length && !check[idx1][idx2+1] && 
					c2[idx2] == out[outIdx]) {
				q.add(new int[] {idx1, idx2+1, outIdx+1});
				check[idx1][idx2+1] = true;
			}
		}
		return false;
	}
}