코딩 인터뷰 완전 분석 215쪽 문제 18.10 풀이

이제 마지막 문제란다. -_-; 

어려운 문제가 나올까봐 긴장하긴 했지만 마지막이라니 왠지 아쉽네잉.

한 번 풀었다가 내가 문제를 잘못 해석한거라서 이전것은 말아먹었다 ㅜㅜ 

문제는 아래와 같다. (새창으로보기)

문제

사전에 등장하고 길이가 같은 두 단어가 주어졌을 때, 한 번에 글자 하나만 바꾸어 한 단어를 다른 단어로 변환하는 프로그램을 작성하라. 변환 과정에서 만들어지는 각 단어도 사전에 있는 단어여야 한다.

[실행 예]

input : DAMP, LIKE
output: DAMP -> LAMP -> LIMP -> LIME -> LIKE

[사전 데이터]

네 글자 단어 - word4

다섯 글자 단어 - word5

 

[심화 문제 - 풀지 않아도 됩니다]

심화문제 1: 가장 적은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다.

심화문제 2: 가장 많은 수의 단어를 써서 변환하도록 프로그램을 작성해봅시다. 단, 변환 과정에서 같은 단어가 두 번 나오면 안됩니다.

다른 사람들 보니 다들 그래프로.. 풀었길래 따라하는건 양심에 걸려서 새롭게 풀어보았다.

처음에 짰던 재귀형식으로 고민하다가 너무 오래 걸려서 새로운 전략을 짰다.

새로운 해결전략은 다음과 같다. (brand new!!)

1. 처음 element set에는 출발 단어 하나만 들어있다. 사전을 뒤적거리면서 distance가 1인 단어들을 모두 표시힌다.

2. 1번 과정에서 표시한 단어들과 distance가 1인 단어들도 모두 표시한다.

3. 더이상 새로운 단어가 추가되지 않을때까지 위 과정을 반복한다. 도중에 정답을 찾으면 바로 return.

한마디로 distance가 1인 집합에 계속해서 끌어들이는 방법이다.

이에따른 코드는 다음과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORD_NUM	8192
#define MAX_WORD_LEN	6

int nwords;
int elem[MAX_WORD_NUM];

char dic[MAX_WORD_NUM][MAX_WORD_LEN];

int makedic(char *fname)
{
	FILE *fp = NULL;

	fp = fopen(fname, "r");

	if (!fp) {
		printf("%s open fail.\n", fname);
		return 0;
	}

	int n = 0;

	while(1)
	{
		n = fscanf(fp, "%s", dic[nwords]);
		if (n == EOF) break;
		nwords++;
	}

	fclose(fp);
	return 1;
}

int distance(char *w1, char *w2, int len)
{
	int count = 0;

	for(int i = 0; i < len; i++) {
		if (w1[i] != w2[i]) {
			count++;
		}
	}

	return count;
}

int getpage(char *word)
{
	for(int i = 0; i < nwords; i++) {
		if (!strcmp(word, dic[i])) return i;
	}

	return -1;
}

int find(char *word, char *target, int len)
{
	int src_idx = getpage(word);

	if (src_idx == -1) return 0;

	elem[src_idx] = src_idx+1;

	while(1)
	{
		int find_newelem = 0;

		for(int i = 0; i < nwords; i++) 
		{
			if (elem[i])
			{
				for(int j = 0; j < nwords; j++)
				{
					if (elem[j] == 0 && distance(dic[i], dic[j], len) == 1)
					{
						// add new element.
						elem[j] = i+1;

						if (!strcmp(dic[j], target)) return j;

						find_newelem = 1;
					}
				}
			}
		}

		if (find_newelem == 0) break;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		printf("Usage: %s dictionary\n", argv[0]);
		exit(1);
	}

	// make dictionary
	if (makedic(argv[1]) == 0) {
		printf("file open fail.\n");
		exit(1);
	}

	// get input
	char src[MAX_WORD_LEN], target[MAX_WORD_LEN];

	scanf("%s %s", src, target);

	// running...
	int rtn = find(src, target, strlen(src));

	if (rtn == 0) {
		printf("IMPOSSIBLE\n");
	} else {
		// make trace
		int idx = rtn, ntrace = 0;
		int trace[MAX_WORD_NUM];

		while(1)
		{
			trace[ntrace++] = idx;
			if (!strcmp(dic[idx], src)) break;
			idx = elem[idx]-1;
		}

		// print trace
		printf("%s", dic[trace[ntrace-1]]);

		for(int i = ntrace-2; i >= 0; i--) {
			printf(" -> %s", dic[trace[i]]);
		}
		printf("\n");
	}

	return 0;
}

trace를 위해서 elem이라는 배열에 어떤 단어로부터 왔는지 해당 index를 저장해두었다. (trace가 더 빡세...)

사전 파일을 보니 7천줄이 안되는 것같아 일단 메모리에 넣어두고 처리하기로 했다.

다음은 시험결과

shell> ./newdic word4.in

damp like

damp -> gamp -> gimp -> limp -> lime -> like

shell> ./newdic word4.in

acne mind

acne -> acre -> agre -> egre -> eire -> mire -> mine -> mind

shell> ./newdic word5.in

worse tasty

worse -> corse -> carse -> carte -> caste -> haste -> hasty -> tasty

shell> ./newdic word5.in

limit zorna

IMPOSSIBLE

damp like 입력에 대한 답이 예시 답안보다 길어서 맘에 안들긴 하지만 정답이긴 하니 뭐.

이제 심화 문제를 좀 더 고민해봐야지 -_-a

################################################################################################

심화문제 1(가장 적은 단어 사용하기) 해결~! 각 단어마다 distance를 저장해둘 필요가 있다. 

코드는 다음과 같이..

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_WORD_NUM	8192
#define MAX_WORD_LEN	6

int nwords;
int dist[MAX_WORD_NUM];
int from[MAX_WORD_NUM];

char dic[MAX_WORD_NUM][MAX_WORD_LEN];

int makedic(char *fname)
{
	FILE *fp = NULL;

	fp = fopen(fname, "r");

	if (!fp) {
		printf("%s open fail.\n", fname);
		return 0;
	}

	int n = 0;

	while(1)
	{
		n = fscanf(fp, "%s", dic[nwords]);
		if (n == EOF) break;
		nwords++;
	}

	fclose(fp);
	return 1;
}

int distance(char *w1, char *w2, int len)
{
	int count = 0;

	for(int i = 0; i < len; i++) {
		if (w1[i] != w2[i]) {
			count++;
		}
	}

	return count;
}

int getpage(char *word)
{
	for(int i = 0; i < nwords; i++) {
		if (!strcmp(word, dic[i])) return i;
	}

	return -1;
}

int find(char *src, char *target, int len)
{
	int src_idx = getpage(src);

	if (src_idx == -1) return 0;

	dist[src_idx] = 1;

	while(1)
	{
		int updated = 0;

		for(int i = 0; i < nwords; i++)
		{
			if (dist[i])
			{
				for(int j = 0; j < nwords; j++)
				{
					if (distance(dic[i], dic[j], len) == 1) 
					{
						// update distance
						if (dist[j] == 0 || dist[j] > dist[i]+1) 
						{
							dist[j] = dist[i]+1;
							from[j] = i;
							updated = 1;
						}
					}
				}
			}
		}

		if (updated == 0) break;
	}

	int target_idx = getpage(target);
	
	if (dist[target_idx]) {
		return target_idx;
	}

	return 0;
}

int main(int argc, char *argv[])
{
	if (argc != 2) {
		printf("Usage: %s dictionary\n", argv[0]);
		exit(1);
	}

	// make dictionary
	if (makedic(argv[1]) == 0) {
		printf("file open fail.\n");
		exit(1);
	}

	// get input
	char src[MAX_WORD_LEN], target[MAX_WORD_LEN];

	scanf("%s %s", src, target);

	// running...
	int rtn = find(src, target, strlen(src));

	if (rtn == 0) {
		printf("IMPOSSIBLE\n");
	} else {
		// make trace
		int idx = rtn, ntrace = 0;
		int trace[MAX_WORD_NUM];

		while(1)
		{
			trace[ntrace++] = idx;
			if (!strcmp(dic[idx], src)) break;
			idx = from[idx];
		}

		// print trace
		printf("%s", dic[trace[ntrace-1]]);

		for(int i = ntrace-2; i >= 0; i--) {
			printf(" -> %s", dic[trace[i]]);
		}
		printf("\n");
	}

	return 0;
}

다음은 시험결과

shell> ./newdic word4.in

damp like

damp -> lamp -> limp -> lime -> like

shell> ./newdic word4.in

acne mind

acne -> aune -> dune -> dine -> mine -> mind

shell> ./newdic word5.in

worse tasty

worse -> torse -> tarse -> tasse -> taste -> tasty

역시 결과가 달라졌다 음하핫. 시간은 좀 더 걸리지만..