- 카드 짝 맞추기
- Python3) 시간 초과가 나는 경우
- BFS 탐색할 때 현재 최솟값보다 더 큰 경우 더 이상 진행할 필요 없음
- 큐에서 뺄 때 확인하는 것과 큐에 삽입할 때 확인하는 것은 시간 상 차이가 존재함
- 큐에서 삭제할 때 확인을 하는 경우, 이미 탐색을 종료할 수 있는데도 불구하고 큐에 먼저 들어있던 다른 요소를 전부 처리하고 나서야 탐색을 종료하게 됨
- 보통은 유의미한 시간 차이가 없음 (아슬아슬하게 통과하지 못했을 경우 참고)
- 0, 1번째 카드 중 어떤 카드를 먼저 뒤집을지 결정할 때 순열, 비트연산자 이용
- 1744 (수 묶기)
- 양수를 담을 벡터와 음수를 담을 벡터를 따로 선언
- 2637 (장난감 조립)
- x(만들어지는 부품) ← y(필요한 부품) 의 관계를 역으로 만들면 루트노드가 완제품이 되고 리프노드가 기본 부품이 됨
- 결국, BFS/DFS 탐색을 통해 필요한 리프노드의 개수를 구하는 문제
- 리프노드 개수만 구하면 되는 문제이기 때문에, 위상정렬 할 필요는 없음.
- 위상정렬을 사용하면 큐에 중복 정점이 들어가지 않기 때문에 탐색 시간을 줄일 수 있음.
- 14907 (프로젝트 스케줄링)
- 입력 cin.eof 처리로 받아야 함 (while문의 조건으로 바로 입력 받는 거 가능)
- 1516 (게임 개발)
- 1766 (문제집)
- 23632 (쿠키런 킹덤)