BFS22 [백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 문제) 백준 - BFS - 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 주어진 첫 소수의 한 자리를 바꾸어 두 번째 소수를 만들 수 있는 최소 변환 수를 구하는 문제였습니다. 에라토스테네스의 체를 활용하여 10000 이하에 대하여 소수 판별(isPrime)을 진행합니다. 그 후 주어진 수의 첫자리부터 4번째 자리까지 변환하면서 소수이면서 방문하지 않은 수에 대하여 queue에 push 하여 BFS를 진행합니다. C++ 소스 코드) Full.. 2022. 3. 16. [백준] 18405번 - 경제적 전염 (C++) 문제 및 풀이 문제) 백준 - BFS - 경제적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS를 통해 바이러스를 전염시킵니다. 매 초마다 전염을 하는데 1번부터 K번 순서대로 전염시켜야 되기 때문에 각 초마다 q_size의 좌표를 벡터에 넣어 정렬을 진행합니다. 정렬을 했다면 BFS를 진행하여 바이러스를 퍼트립니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BO.. 2022. 3. 2. [백준] 12851번 - 숨바꼭질 2 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/12851_%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%882.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutio.. 2022. 3. 1. [백준] 18243번 - Small World Network (C++) 문제 및 풀이 문제) 백준 - BFS - Small World Network https://www.acmicpc.net/problem/18243 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net 1부터 N까지 시작하여 각 사람마다 거리를 구하여 6번 안에 이어져있는지 확인합니다. 가중치가 없는 간선으로 이어져 있으므로 BFS를 활용합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/mai.. 2022. 2. 27. [백준] 6118번 - 숨바꼭질 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 https://www.acmicpc.net/problem/6118 6118번: 숨바꼭질 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 2022. 2. 19. [백준] 19238번 - 스타트 택시 (C++) 문제 및 풀이 문제) 백준 - BFS - 스타트 택시 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net BFS를 통해 택시에서 승객, 승객에서 목적지까지의 최단 거리를 연료를 고려하여 승객을 태웁니다. board: 택시가 활동할 영역의 지도이며 -1일 경우 벽, 0일 경우 빈칸, 1 이상일 경우 손님의 인덱스를 나타냅니다. tempBoard: BFS를 진행할때 거리와 방문 여부를 함께 저장합니다. coords: 승객의 좌.. 2022. 2. 10. [백준] 18513번 - 샘터 (C++) 문제 및 풀이 문제) 백준 - BFS - 샘터 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net BFS를 통해서 각 샘터를 기준으로 지을 수 있는 집의 최소 불행도를 구한다. 주언진 샘터의 좌표를 Queue에 push 하여 매번 Queue size마다 K개 집에 대하여 거리를 더해준다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Prob.. 2022. 2. 3. [백준] 5427번 - 불 (C++) 문제 및 풀이 문제) 백준 - BFS - 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 불이 번지는 BFS, 상근이가 탈출하기 위한 BFS를 따로 돌려서 상근이가 탈출할 수 있는 최소 시간을 구합니다. 매 Test Case마다 visited배열과 Fire배열을 초기화하는 것을 잊지 맙시다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/542.. 2022. 1. 24. [백준] 7569번 - 토마토 (C++) 문제 및 풀이 문제) 백준 - BFS - 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS를 통해 해결했습니다. Queue에 익은 토마토를 넣어주고 dist배열을 통해 방문 여부와 시간을 memo 합니다. 배열에 토마토 익힘 여부를 표시하여 BFS 종료 후, 안 익은 토마토가 있다면 -1을 출력하고 다 익었다면 dist 배열에서 최댓값을 출력합니다. C++ 소스 코드) Full Code) https://github.com/.. 2022. 1. 8. 이전 1 2 3 다음 반응형
