[2주차_금요일] 43163_단어 변환

[baexxbin]

• 사이트: 프로그래머스
• 문제: 단어 변환
• 번호: 43163
• 레벨: Level3

[KodaHye]

🤔 시간복잡도 고려사항

• begin에 대해 직접 한 단어씩 바꾸면서 target을 찾을 경우 시간 복잡도는 26^10 이 될 수 있음
• BFS로 구현: O(N * 단어의 길이), N: 단어의 종류
  • 단어의 길이를 곱하는 이유: 두 단어 사이 다른 알파벳 개수를 구하기 때문

💡 풀이 아이디어

• 단어 배열을 탐색하며 현재 자신의 숫자와 다른 알파벳의 개수가 1개일 때 Queue에 넣어줌
• Queue: Node에 대한 정보를 담을 수 있음
• Node: idx와 depth를 가지고 있음
• boolean v[]: 해당 idx의 단어가 쓰였는지 확인하는 배열

[Jewan1120]

🤔 시간복잡도 고려사항

• 3 ≤ words의 길이 ≤ 50 → 완전 탐색을 이용해도 무리가 없음

💡 풀이 아이디어

• 현재 단어에서 변환할 수 있는 값들은 정해져 있으므로 최소 횟수를 구하기 위해 BFS를 진행
• BFS를 진행하되 깊이를 나타내기 위해서 깊이마다 큐에 몇 개가 들어있는 지를 파악 후 그 수만큼 진행

[yeongleej]

🤔 시간복잡도 고려사항

각 단어길이 <= 10 words 길이 <= 50 => 정점의 개수 (N) == words 길이, 즉 O(N^2)이어도 괜찮음 => 완전탐색 고려(BFS, DFS 등) 💡 풀이 아이디어

BFS로 풀이 현재 단어(now)와 다음 탐색할 단어(next)가 하나의 알파벳만 차이나면 해당 단어로 이동할 수 있음 => 큐에 삽입

[icegosimperson]

🤔 시간복잡도 고려사항 3<= 단어 길이 <=10, 단어개수 <=50, O(N^2) 이상 가능

💡 풀이 아이디어 단계별로 진행하여 최단 경로 찾기 -> BFS(Queue, boolean[] visited) 최소 변환 과정(convert) : 한글자만 다를 경우 변환

[baexxbin]

🤔 시간복잡도 고려사항

• 3<= 각 단어 길이 <=10
• 3<= words 길이 <=50
• 완전탐색 가능 O(N^2)

💡 풀이 아이디어

• words안에 있는 단어들 중 한 글자차이나는 단어로 변환해가야함
• dfs이용: 현재 단어가 target이랑 같아질때까지 진행
  • 사용하지 않은 단어이고 !visited[i], 한글자 차이나면(canChange(cur, nxt)) cnt++

문제를 잘 읽고 이해하자..

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: BFS
• 시간복잡도: 3 <= words <= 50 크기로 BFS 가능

💡 풀이 아이디어

• bfs 를 활용 해 최소값(최단거리)를 어떻게 찾을 수 있는지? 이동할 수 있는 단어의 갯수만큼 너비 탐색 진행 > 너비 탐색이 끝났다면 현재 단어에서 인접 단어들 까지의 거리가 각각 1 이라는 뜻 한번의 너비 탐색이 끝나면 해당 레벨의 최단거리 탐색 종료 > 다음 레벨 탐색
• visited 를 어떤 목적으로 활용하는지? begin에서 target으로 변환하는 단게의 최소 횟수를 전체적으로 탐색하므로 이미 방문했을 경우 방문 하지 않는다