[백준] 9019 DSLR

문제 설명

BFS를 사용하여 최소 연산 횟수로 타겟숫자를 만드는 방법의 커맨드들을 공백없이 출력하는 문제

visited

• 연산 결과로 만들어진 수가 아직 이번 연산결과 외에 만들어 진적이 있는지 없는지 판단하고 만들어 진적이 없을 때만 진입하도록 설계
• 이전에 연산된 이력이 있는 숫자라면 최소 연산횟수로 현재 현산 결과로 도달한것이 아니다 따라서 문제의 조건과 맞지 않아 무의미함

q

• 현재 숫자를 가지고 만들어진 결과 숫자들로 다음 연산 후보들이 저장되어 있음
• 이 연산 후보자들이 다음 연산결과로 타겟숫자가 될 수 있음
• 해당 숫자들은 자신이 만들어진 최소 연산 결과를 짝으로 같이 가지고 다녀야 타겟 넘버가 되는 순간 그전 연산결과들 + 마지막 연산 결과를 더해 답을 구할 수 있음
• tuple을 사용하여 (연산과정, 현재 숫자)의 형태로 구현

문제 링크

https://www.acmicpc.net/problem/9019

겪은 문제

• 시간초과
  • deque를 import 하지 않고 pop(0)로 해결 하려고 했음
• BFS 문제를 풀다보면 거쳐간 적이 있음을 표시하기 위해 visited를 list나 set의 형태로 많이 나타내는데 시간 복잡도상 둘은 차이가 없다. 어느 것을 써도 무방
  • 특정 index를 알 때 list look up 시간 복잡도 O(1)
  • set은 해시테이블로 look up, insert, delete의 시간 복잡도 모두 O(1)
  • 하지만 list 사용시 특정 index로 명시하지 않고 특정 값을 찾는다면 O(n)이니 주의

코드는 여기서

ref)
1. https://paris-in-the-rain.tistory.com/94
2. https://velog.io/@ggyungjun0913/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%82%B4%EC%9E%A5%ED%95%A8%EC%88%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84