[2021년 08월 08일 17시 18분 작성] [PS][BFS] BOJ 9177 : 단어 섞기 [문제 링크 : 클릭] 1. 풀이 분류는 DP 문제였지만, BFS를 통해 해결하였습니다. 상태 노드는 int형 정수쌍 {a, b}로 정의합니다. {a, b} : str[0]은 a번째 문자를 뽑을 차례이고, str[1]은 b번째를 뽑을 차례 --> 이를 기반으로 메모이제이션을 적용해도 됩니다. {0, 0}부터 시작해서 두 개의 문자열 중에 하나를 뽑아 BFS를 진행하며 답을 찾습니다. +) 분기마다 방문 여부와, 다음 상태 노드가 정답 문자열로 옳게 나아가는지 판단하고, a와 b가 각 문자열의 길이를 넘지 않도록 조건을 걸어주었습니다. 그러면 현재 노드의 a+b가 str[2]의 길이가 같다면, 정답을 찾은것이므..
