[프로그래머스] 깊이/너비 우선 탐색(DFS/BFS) - 단어변환

고민중인 문제!-! 기록용

두 개의 단어 begin, target과 단어의 집합 words가 있습니다.

아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.

 

1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.

2. words에 있는 단어로만 변환할 수 있습니다.

 

예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다.

두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함수를 작성해주세요.

 

 

제한사항

• 각 단어는 알파벳 소문자로만 이루어져 있습니다.
• 각 단어의 길이는 3 이상 10 이하이며 모든 단어의 길이는 같습니다.
• words에는 3개 이상 50개 이하의 단어가 있으며 중복되는 단어는 없습니다.
• begin과 target은 같지 않습니다.
• 변환할 수 없는 경우에는 0를 return 합니다.

입출력 예

begin	target	words	return
hit	cog	[hot, dot, dog, lot, log, cog]	4
hit	cog	[hot, dot, dog, lot, log]	0

 

입출력 예 설명

예제 #1
문제에 나온 예와 같습니다.

 

예제 #2
target인 cog는 words 안에 없기 때문에 변환할 수 없습니다.

 

2020.07.11

어떻게 접근을 할까?

1. 명백한 반환 조건!!

다른 항목을 비교하기 전에 체크해야 할 점.

target값이 words에 없는 경우 최종적으로 변환 할 수 없으므로 0을 리턴해주자.

 

2. 다음으로는 그래프를 만든다.

begin값과 words의 요소들을 포함한 그래프를 만든다.

begin 노드를 하나 생성한다.

words의 모든 요소를 돌면서 그래프의 노드에서 글자가 하나만 다른 노드와 연결해준다.

 

3. 그렇다면 글자가 다른건 어떻게 비교할까? - 함수를 만들어야지

단어1과 단어2를 인자로 받는다.

count값은 0

단어1과 단어2의 길이는 같으므로, i를 0부터 (단어길이-1)까지 반복

반복문을 돌면서 단어1[i], 단어2[i]가 다르면 count를 1 증가시켜준다.

최종적으로 count가 1인 두 단어가 노드로써 연결될 수 있다는 말~

 

4. 여기서 그럼,, 그래프까지 만들었으니 begin부터 target 노드까지의 최단 거리를 구하면 되지 않을까?

 

이런 과정으로 풀어 나가 볼 생각이다....

BFS, DFS를 어떤 식으로 적용할지는 아직 고민중!

---

 

2020.07.13

그래프 구현하기

객체지향 언어인 Java를 사용할 때는 그래프를 구현할 때 보통 Node클래스를 만들어 구현했었다.

ex)

Class Node(){
    String value;
    ArrayList<Node> children;
    
    public Node(value){
    	self.value = value;
        self.children = new ArrayList<>();
    }
    
    addChild(child){
    	self.children.add(child);
    }
}

 

파이썬을 사용하다보니 클래스는 웬만하면 안만들게 되었다...

사실 클래스 만드는편이 좋은지 아닌지는 잘 모르겠지만, 만들지 않아도 잘 풀렸다!

이번에는 딕셔너리로 구현했다. 딕셔너리는 해시값을 사용하기 때문에 탐색하는 데에 O(l)이 소요된다고 한다.

key값은 단어 문자열, value값은 key값과 한 글자 차이나는 단어들의 리스트로 구성하였다.

 

그렇게 완성된 그래프

{"hit":["hot"],

"hot":["hit","dot","lot"],

"dot":["hot","dog","lot"],

"dog":["dot","log","cog"],

"lot":["hot","dot","log"],

"log":["dog","cog"],

"cog":["dog","log"]}

graph = {}
    
## begin : word
for word in words:
    if strCmp(begin, word) == 1:
        if word in graph:
            graph[word].append(begin)
        else:
            graph[word] = [begin]
        if begin in graph:
            graph[begin].append(word)
        else:
        	graph[begin] = [word]
                
## word : word
for i in range(len(words)):
    for j in range(i+1, len(words)):
        if strCmp(words[i], words[j]) == 1:
            if words[i] in graph:
            	graph[words[i]].append(words[j])
            else:
            	graph[words[i]] = [words[j]]
            if words[j] in graph:
            	graph[words[j]].append(words[i])
            else:
            	graph[words[j]] = [words[i]]
       

 

---

2020.07.13

단어 비교하는 함수

두 단어를 비교하여 몇글자가 다른지 리턴하는 함수를 만들어보자.

def strCmp(word1, word2):
    # 두 글자의 길이가 다르면 비교 불가능
    if len(word1) != len(word1):
        return -1
    
    count = 0
    for i in range(len(word1)):
        if word1[i] != word2[i]:
            count += 1
            
    return count