에라토스테네스의체 (1) 썸네일형 리스트형 [백준] 1963번: 소수경로 (C++ 풀이) 문제 https://www.acmicpc.net/problem/1963풀이BFS+소수 구하기 문제이다.1.네 자리수에 대하여 각 자리수의 숫자를 바꿔가면서 모두 탐색해보면 된다.탐색조건은 1. 아직 방문하지 않은 숫자 2. 소수 3. 1000~9999인 숫자 이다. 2.테스트 케이스 입력받기 전에, 일단 나는 소수를 미리 구해놓았다.소수를 구하는 방법 중에 '에라토스테네스의 체'를 이용하여 1차원 bool형의 배열에 1부터 9999까지 소수면 false, 소수가 아니면 true를 저장해놓았다.'에라토스테네스의 체'의 시간복잡도는 O(Nlog(logN))이다. 배열에 먼저 소수인지 아닌지 체크만 해놓으면 나중에 BFS하면서 방문할때 해당 수가 소수인지 아닌지 바로 배열로 참조가능하므로 상수시간으로 체크할 .. 이전 1 다음
