[ boj : 3257 ] 발코딩

www.acmicpc.net/problem/3257

3257번: 발코딩

문제 : 창영이과 강산이가 생각한 단어를 입력하고, 이 알파벳들을 서로 번가라가면서 입력하여 새로운 문자열을 만듭니다. 이때 창영이가 입력한건 1, 강산이가 입력한건 2 일때 새로운 문자열을 누가 입력했는지 출력하세요. 다수의 답 중 하나만 출력하면 됩니다.

 

해설 : 이런 문제에 정말 취약합니다. 문제를 보면 어떻게 '모델링'해야되는지 보이지가 않습니다. 현재 선택을 했을때 만들어질 수 있는 답의 케이스가 달라지고 이를 어떻게 처리해야 될지 잘 모르겠더라구요.

 

생각을 해보면 모든 케이스들을 전부 확인하기에는 많은 시간이 걸립니다. 문자열이 각각 150 씩이니 중복된 케이스들만 해도 엄청나겠죠.

 

그러면 어떻게 중복을 걸러낼 수 있을까요??

그리고 어떻게 새로운 문자열을 만들 수 있을까요?

 

먼저 문자열을 만드는 방식부터 천천히 생각해봅시다. 창영이든 강산이든 누가 먼저 시작하든 관계없이 새로운 문자열을 만들기 위해선 두명이 입력한 문자열에서 '선택'을 해야합니다.

그럼 우린 이를 그래프로 치환해서 바라볼 수 있겠죠.

즉, O(nm)의 시간복잡도로 해결할 수 있는 BFS 를 사용해서 끝까지 탐색을 할 수 있습니다. 

 

자 그럼 특정한 상태를 선택할 수 있는 방법은 찾았으니 우린 먼저 방문했던 케이스를 다시 방문하지 않도록 하기 위한 중복처리를 해주어야 합니다.

 

이때 정말정말 강조드리고 싶은건, 흔히들 BFS 문제라고 생각해보면 전형적인 문제

즉, 굳이 생각하지도 않아도 그래프로 표현되는 문제들만 접해오신 분들이 대다수라고 생각하는데 이때 많은 분들이 '좌표' 값을 기준으로 방문배열을 생성합니다.

그러나!!!절대로 절대로 앞으로는 이렇게 생각하지 마시길 바랄게요....ㅠㅠ

 

우린 그래프를 탐색할때 '방문배열'이 아닌 '상태배열'이라고 생각합시다.

이게 무슨뜻이냐면 단순히 2차원 배열이 주어지고 방문했는지 확인만 하면 되는 문제들과는 달리 현재 어떤 선택을 했을때 좌표값만이 아닌 도출되는 정답의 상태를 변화시켜야 하는 문제들이 많기 때문입니다.

 

지금 보고 있는 이 문제 또한 마찬가지 입니다. 문제에서 절대로 '좌표'값은 찾아 볼 수도 없으며 대체 어떤 기준으로 중복 처리를 해야하냐?!!!라고 의문점이 들 수 있는데 이를 '상태'값으로 바라본다면 우린 창연이가 선택을 하는 행위와 강산이가 선택을 하는 행위를 통해 문제의 정답이 달라진다는 것을 알 수 있습니다.

그럼 이것을 기준으로 '상태배열'을 만들면 된다는 뜻입니다.

 

다시 정리하면 BFS를 실행하실때 항상 '상태'를 결정하는 '변수'가 무엇인지 생각하세요.

그리고 큐에 삽입할때는 '상태'를 결정하는 변수를 삽입하시고(이때는 상태를 결정하는 변수가 아닌 값들도 삽입해도 문제없습니다) 

이 상태를 결정하는 변수들을 기준으로 '상태배열'을 생성하여 중복처리를 해주시면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

struct info{
	int l,r;
	string s;
};

int visit[151][151];
string n,m,x;
string bfs();

int main() {
	
	cin>>n>>m>>x;
	
	cout<<bfs();
	return 0;
}
string bfs()
{
	queue<info> q;
	string temp = "";
	if(n[0]==x[0]){
		q.push({1,0,temp + '1'});
		visit[1][0]=1;
	}
	if(m[0]==x[0]){
		q.push({0,1,temp + '2'});
		visit[0][1]=1;
	}
	
	int cnt=1;
	while(!q.empty()){
		int size = q.size();
		for(int i=0;i<size;i++){
			info cur = q.front();
			q.pop();
			
			if(cur.l==n.length() && cur.r==m.length())return cur.s;
			
			if(cur.l<n.length() && !visit[cur.l+1][cur.r] && n[cur.l]==x[cnt]){
				q.push({cur.l+1,cur.r,cur.s+'1'});
				visit[cur.l+1][cur.r]=1;
			}
			if(cur.r<m.length() && !visit[cur.l][cur.r+1] && m[cur.r]==x[cnt]){
				q.push({cur.l,cur.r+1,cur.s+'2'});
				visit[cur.l][cur.r+1]=1;
			}
		}
		cnt++;
	}
}