알고리즘
[Java] 백준 9177번 단어 섞기
J3SUNG
2023. 7. 26. 03:10
728x90
두개의 단어의 문자를 하나씩 뽑아서 세번째 단어를 만들 수 있는지 구해야합니다.
BFS로 모든 경우의수를 탐색합니다.
방문배열에 왼쪽과 오른쪽의 인덱스를 넣어서 방문처리합니다.
같은 인덱스로 방문한 경우 처리하지 않습니다.
왼쪽과 오른쪽이 해당 문자를 전부 탐색한 경우 yes를 출력
Queue가 비어져서 나오게 될 경우 no를 출력합니다.
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));
StringTokenizer st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
String result;
for (int ts = 1; ts <= t; ++ts) {
st = new StringTokenizer(br.readLine());
String A = st.nextToken();
String B = st.nextToken();
String str = st.nextToken();
int[][] visit = new int[201][201];
Queue<Pair> q = new LinkedList<>();
int left = 0;
int right = 0;
int index = 0;
result = "no";
q.add(new Pair(left, right, 0));
while (!q.isEmpty()) {
left = q.peek().left;
right = q.peek().right;
index = q.peek().index;
q.poll();
if (visit[left][right] == 1) {
continue;
}
visit[left][right] = 1;
if (left == A.length() && right == B.length()) {
result = "yes";
break;
}
if (left < A.length() && A.charAt(left) == str.charAt(index)) {
q.add(new Pair(left + 1, right, index + 1));
}
if (right < B.length() && B.charAt(right) == str.charAt(index)) {
q.add(new Pair(left, right + 1, index + 1));
}
}
bw.write("Data set " + ts + ": " + result + "\n");
}
bw.close();
}
public static class Pair {
int left;
int right;
int index;
public Pair(int left, int right, int index) {
this.left = left;
this.right = right;
this.index = index;
}
}
}