취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 9177번 문제인 단어 섞기이다.
문제는 아래 링크를 확인하자.

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

주어지는 세 단어를 차례대로 s1, s2, s3라 하자. s1의 i번째 문자와 s2의 j번째 문자까지로 s3의 i+j번째 문자까지 만든 경우를 노드 (i,j)와 같이 나타내고, 각 (i,j) 상태에서 s1 또는 s2의 문자 하나를 다음 문자로 사용해 (i+1,j) 또는 (i,j+1)의 상태로 만들 수 있는 관계를 방향이 있는 에지로 나타내면 문제의 상황을 DAG로 모델링할 수 있게 된다.

위 DAG에서 (0,0)에서 출발해 (s1의 길이, s2의 길이)까지 도달할 수 있는지를 살펴 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

string s1, s2, s3;
int visited[201][201];

void dfs(int idx1, int idx2) {
	if (visited[idx1][idx2]) return;
	visited[idx1][idx2] = 1;
	if (s1[idx1] == s3[idx1 + idx2]) dfs(idx1 + 1, idx2);
	if (s2[idx2] == s3[idx1 + idx2]) dfs(idx1, idx2 + 1);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	for (int t = 1; t <= T; t++) {
		memset(visited, 0, sizeof(visited));
		cin >> s1 >> s2 >> s3;
		int s1len = s1.length(), s2len = s2.length();
		s1 += '*', s2 += '*', s3 += '#';
		dfs(0, 0);
		if (visited[s1len][s2len]) cout << "Data set " << t << ": yes\n";
		else cout << "Data set " << t << ": no\n";
	}
}