[ BFS/DFS/C++ ] 프로그래머스 - 단어 변환

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43163

풀이

접근법 1. 백트래킹(DFS)

문제의 핵심

• begin에서 target으로 변환하는 최소 단계 수를 찾아야 한다.
• 한 번에 한 개의 알파벳만 변경 가능하며, 변경 후 단어는 words 리스트에 포함되어 있어야 한다.

종료 조건

target 문자열과 현재 문자열이 같으면 재귀함수가 종료된다.

매개변수

• target 문자열
• 현재 문자열 : words 배열의 요소 문자열
• 현재의 단계 (몇 개의 단어를 거쳤는지)
• 현재까지 진행한 과정 중 최소 단계 (이 문제의 답)
• 방문 확인 배열 : words 배열 요소 방문 확인해야함
  
  

DFS 탐색 흐름

현재 단어가 target과 같다면 종료
→ 최소 단계(minStep) 갱신 후 재귀 종료.

변환 가능한 단어 탐색

words 리스트를 순회하면서 한 글자만 차이나는 단어 찾기.
해당 단어를 방문하지 않았다면 방문 처리 후 DFS 호출(단계 +1).
백트래킹 수행

탐색이 끝난 후, 다시 방문을 취소하여 다른 경로 탐색 가능하게 함.

의사 코드

// 변환 가능한 단어 탐색: 하나의 알파벳만 다른지 확인하는 함수
bool FindDiffOneLetter(string a,string b)
{
	로직 구현
}
// 

// dfs 함수
void func(string target, string 현재 문자열, vector<string>& words, vector<bool>& visited, int &answer, int step)
{
	if(target 문자열과 현재 문자열이 같으면)
    {
    	answer 최소값 업데이트
    	재귀함수가 종료
    } 
    
    for(int i =0; i<words.size(); ++i)
    {
    	// 변환 가능한 단어 탐색, 방문 확인
    	if(FindDiffOneLetter(현재 문자열, words[i]) && false == visited[words[i]])
        {
        	// 방문 처리
        	visited[words[i]] = true;
            func(target, words[i], words, visited, answer, step+1);
            // 백트래킹
            visited[words[i]] = false;
        }
    }
}

---

접근법 2. BFS(너비우선탐색)