01039번 교환

Problem link: https://www.acmicpc.net/problem/01039

Keywords: Graph, Breadth first search

풀이를 고민하다가 (얼마 하지도 못했는데…), 알고리즘 분류 항목이 눈에 보여서 풀려버렸다… 이제 보기 메뉴에서 꺼놓았다. 문제 자체는 특별한 지식을 필요로하지 않아서, 면접용 문제로 아주 좋아보인다.

문제는 BFS (자신 있다면, DFS도 상관 없음) 로 풀 수 있는데,

• VISIT[k][n]: k번 교환 수행으로 n을 만드는 경우와 같이 방문 배열을 설정한 뒤에,
• BFS를 수행하고,
• VISIT[K][i]가 true인 최대의 i를 고르면 된다.

솔루션은 여기 에서 확인할 수 있다.