프로그래머스 (단어 변환, 깊이/너비 우선 탐색(DFS/BFS)) C++

프로그래머스 (단어 변환, 깊이/너비 우선 탐색(DFS/BFS)) C++

728x90

DFS가 아니라 BFS 인것 같긴한데 일단 함수명은 이렇게 dfs로 해버렸다. 아닌가... 아직 개념이 확실히 잡히진 않은듯.. 아무튼 DFS와 BFS를 할 때 파라미터로 하나씩 바뀌어서 넘겨지게 되는 것에 Focus를 맞춘다. 그리고 visited가 가장 중요!! 그리고 이 문제의 경우 방문하지 않은 경우의 node를 queue에 모두 넣고 살피는 것이 아니기 때문에 dfs 재귀를 탈출하게 되면 이중 for문 중 nested된 for문에서 visited 한 노드의 visited를 0으로 만들어야 한다는 것이 포인트

#include #include #include using namespace std; int answer = 100; string value; vector visited(50,0); void dfs(string begin, string target, vector words, int result) { if(begin == target) { if(answer > result) answer = result; return ; } // word 배열에 들어있는 개수만큼 반복 for(int i = 0 ; i < words.size() ; i++) { // count 변수는 for문을 돌 때마다 초기화를 해줘야 한다. int count = 0; // words 배열의 단어 크기만큼 반복을 하면서 일치하지 않는 문자의 개수를 세준다. for(int j = 0 ; j < words[i].size() ; j++) { if(begin[j] != words[i][j]) count++; } // 틀린 문자의 개수가 1개이면 DFS를 실시한다. if(count == 1) { // 만약 해당 단어를 방문하지 않았으면 if(visited[i] == 0) { // 방문을 하고 visited[i] = 1; // DFS를 진행한다. dfs(words[i], target, words, result+1); /* DFS를 탈출했다는 것은 begin == target의 상황을 만났고 해당 answer에 result 값을 넣었다는 것이다. 이를 다시 0으로 바꾸는 이유는 이전 begin에서 Spell 이 1개가 다른 단어가 여러 개 존재하기 때문에 해당하는 단어로도 바뀔 수 있어야 모든 경우의 수를 탐색하는 경우가 되기 때문이다. */ visited[i] = 0; } } } } int solution(string begin, string target, vector words) { dfs(begin, target, words, 0); // 만약 answer가 100이면 result가 바뀌지 않았다는 것이고 바뀔 수 없다는 것 if(answer == 100) answer = 0; return answer; }

from http://handong201.tistory.com/122 by ccl(A) rewrite - 2021-12-30 12:01:12