[DFS/BFS] 단어 변환

 

* 풀이 방법

 

1) 우선, 설명에서 시작점과 끝점이 존재하고 시작에서 끝까지 도달한다 = 그래프 순회 생각할것.

2) 이동시, 깊이나 레벨을 기준으로 이동한다면 BFS를 고려해야함

3) 최적 거리를 파악해야한다 = BFS를 생각할것

 

* BFS 구현 방법

 

1) BFS 구현 필요 조건

 

- 방문 여부 변수 (ex) visited 변수)

- 방문 방법 ( ex) 동서남북, 좌우측...)

- 방문 가능 조건 ( ex) 인접행렬시, 1)

- 현재 방문 표시용 인덱스 (ex) 좌표, idx)

 

2) 구현 

 

 - 방문 표시용 인덱스를 받는 queue 선언. 

 - 방문 방법만큼 이동후, 방문 가능 조건 판단.

 - 조건 만족시, 방문 여부 변수 update & 방문 표시용 인덱스 증가.

 

=> q.empty() 될때까지 반복.

 - 만약 원하는 값을 저장하는 변수가 따로 존재하지 않는다면, 원하는 조건에 도달시 break.

 - 원하는 값을 저장하는 변수가 따로 존재한다면, empty() 될 때까지 반복 후 원하는 조건의 값 출력
    (ex) 게임 최적거리의 dist[n-1][m-1] )