프로그래밍74 [bfs] 백준 1963 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야" “그럼 8179로 해” “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. www.acmicpc.net 소수는 에라토스테네스의 채를 이용해서 구했습니다. 처음에 풀 때는 queue에 넣을 값을 찾기 위해 1000부터 9999까지 모두 뒤졌습.. 2019. 4. 1. [bfs] 백준 2589 보물섬 https://www.acmicpc.net/problem/2589 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 가로, 세로의 크기는 각각 50이하이다. www.acmicpc.net 모든 정점을 돌아다니면서 bfs를 수행하면서, 시간을 증가시킵니다. 그리고 ret 변수를 최대 시간으로 계속 갱신합니다. #include #include #include using namespace std; int main(){ char map[51][51]; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int ret .. 2019. 4. 1. [dfs] 백준 11403 경로 찾기 https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net #include #include using namespace std; vector v[100]; int ret[100][100] = {0}; int n; void dfs(int start, int y){ for(int i = 0; i < v[start].size(); i++){ int tmp = v[start][i]; if(ret[y][tmp]) continue; ret[y][tmp] = 1; dfs(tmp,y); } } int main(.. 2019. 3. 27. [bfs] 백준 1389 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. www.acmicpc.net #include #include #include using namespace std; int main(){ vector arr[101]; bool.. 2019. 3. 27. [dfs] 백준 2644 촌수계산 https://www.acmicpc.net/problem/2644 12345678910111213141516171819202122232425262728293031323334#include #include using namespace std;vector v[100];bool visited[100] = {0};bool chk = 0; void dfs(int start, int target, int ret){ if(start == target) {cout > target1 >> target2 >> m; for(int i = 0; i > x >> y; v[x].push_back(y); v[y].push_back(x); } dfs(target1,target2,0); if(!chk) cout 2019. 3. 27. [dfs] 백준 9903 로또 https://www.acmicpc.net/problem/6603 간단한 dfs문제입니다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;int arr[13];int t = 0; void dfs(int start, vector& v){ v.push_back(arr[start]); if(v.size() == 6){ for(int i = 0; i 2019. 3. 27. 이전 1 2 3 4 5 6 ··· 13 다음