[프로그래머스][Java] lv3 단어변환 (DFS/백트래킹) - 문제풀이 및 팁

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

코딩테스트 연습 - 단어 변환

 

문제요약

주어진 단어(begin)를 배열(words)에 있는 단어 중 한글자만 다른 단어랑 바꿔 목표단어(target)를 만들고 바꾼 횟수찾기

 

풀이

 

1. dfs 수행

2. 다음노드 탐색시 조건체크(유망성)

3. 한 노드 기준으로 탐색이 끝나면 부모노드로 back & 탐색

 

---

- 정해진 그래프를 탐색하는 것이 아니라, 탐색하면서 다음 노드를 선정하며 탐색 (노드만 주어짐)

- 조건을 통해 탐색 최적화

 

- begin은 words에 포함되어 있지 않음

- begin은 target과 같지않음

 

소스코드

https://github.com/999inim/Algorithm/blob/main/programmers/PS48.java

 

---

API 정리 및 팁

1. 배열에 어떤 요소가 포함되어있는지 여부 확인

Arrays.asList(words).contains(target)

반복문으로 찾아도되나, 리스트 인터페이스에서 제공하는 cotians를 이용.

 

2. 그래프 탐색

// 다음 노드 찾는 반복문 내부코드 일부
for ...
	if ... {
        visited[i] = true;
        dfs(words[i], target, words, level+1);
        visited[i] = false;
    }
}

(1) 콜스택에 함수가 어떤 순서로 쌓이는지 

(2) 그래프상에서 노드를 탐색하는 순서 (부모 노드로 돌아가는 시점등)

 

3. dfs의 파라미터

static boolean[] visited;
static int answer = 0;
...
dfs(String current, String target, String[] words, int level) { ... }

 

 

값을 넘겨줄 것인지, static으로 뺄 것인지 결정

---

느낀점

1. 예시를 직접 써보며 흐름이해

2. 디버깅 시점, 구간별 분석시 흐름 놓치지 않기

변수 상태등을 정확히 추적, 검증

3. 느낌이나 확실하지 않은 논리는 구체적으로 표현