확실히 쉴 수 있는 날이여서 그런지 문제를 푸는데 더 집중을 했고 시간이 생각보다 많이 나서 문제를 더 풀어보았다. BFS 관련 문제지만 사실 이 문제는 DP로도 Memoization 방법을 통해서도 풀 수 있는 문제다. 내 전 포스트에서 정리했던 DP 관련 문제에 이렇게 비슷한 문제가 나왔었고 아마 Memoization 을 활용한 2차원 DP 벡터를 사용했다면 똑같이 풀었을수도 있었다. 그러나 난 BFS방식에 집중을 했고, 여느때나 그러듯 첫 시도는 실패했다. 첫 시도는 메모리 초과로 실패 했었고 자세히 문제를 읽어본 결과 꽤 많이 중복되는 부분이 많은것을 visited 로 확인을 안하고 탐색을 할려니 틀릴 수 밖에 없었던거같다.
일반적인 Matrix를 이용한 탐색이 아닌 이런 류의 문제는 전에도 몇번 풀어보았고, 핵심은 주어진 모든 상황에 대해서 대입을 한번씩 해줘야 한다는것이다. 한마디로 "완전탐색" 에 가까운 문제인데 중복되는 탐색 범위는 visited 로 피해주는게 이 문제의 핵심이 아닐까 싶다.
처음에 만들어줬던 세팅. 똑같이 struct를 만들어줘서 화면에 나오는 숫자, 클립보드에 숫자, 그리고 시간을 설정 해주었다.
struct를 활용한 방법은 좋긴 하지만 그 값을 설정 해줘야하는게 좀 불편한거같다. 좀 더 익숙해지면 다른 방법을 쓰고싶다. 여튼, 핵심은 visited 벡터안에 화면의 숫자, 클립보드의 숫자로 컨트롤 해주었단 건데 복사 하는 과정에서 최대 1000 + 1000 의 숫자가 나올수 있기에 저렇게 만들어주었다.
그 외에는 굉장히 평범한 방법이었지만 약간의 DP 방법을 섞은 BFS 가 아니였나 싶긴하다.
배운점:
1. BFS에서 활용되는 visited 의 다양한 예
2. struct 활용
