설비 잠금 코드 최소 변경 횟수

문제

공장 설비의 제어판은 길이가 같은 숫자 코드로 잠겨 있습니다. 현재 코드 begin을 목표 코드 target으로 바꾸려고 합니다.

제어판에는 두 가지 규칙이 있습니다.

1. 한 번에 한 자리 숫자만 바꿀 수 있습니다.
2. 숫자를 바꾼 직후의 코드는 반드시 승인 목록 codes에 있어야 합니다. 승인되지 않은 코드가 만들어지면 설비가 잠기므로 그런 변경은 할 수 없습니다.

begin은 승인 목록에 있을 수도, 없을 수도 있습니다(현재 사용 중인 코드이므로 그대로 두는 것은 문제되지 않습니다).

begin, target, 승인 목록 codes가 주어질 때 target에 도달하기 위한 최소 변경 횟수를 반환하는 solution(begin, target, codes) 함수를 작성하세요. 어떤 방법으로도 도달할 수 없으면 -1을 반환합니다. 이미 begin과 target이 같으면 0입니다.

예시

예시 1 설명: 230 → 231 → 731로 두 번 만에 도달합니다. 230에서 731로 곧장 가려면 두 자리를 동시에 바꿔야 하므로 불가능합니다.

예시 2 설명: 목표 코드 731이 승인 목록에 없어 만들 수 없습니다.

예시 4 설명: 0000 → 0100 → 0120 → 0123으로 세 번입니다. 중간 코드가 모두 승인 목록에 있어야 하므로 곧장 0123으로 갈 수 없습니다.

제약 조건

• 2 ≤ begin, target, codes[i]의 길이 ≤ 8이며 모두 길이가 같습니다.
• 모든 코드는 '0'~'9' 문자로만 이루어집니다.
• 1 ≤ codes.length ≤ 200
• 승인 목록에 같은 코드가 두 번 이상 나올 수 있습니다.

시간 복잡도 목표: O(n² × L) — n은 승인 코드 수, L은 코드 길이

공간 복잡도 목표: O(n)