BFS22 [백준] 9372번 - 상근이의 여행 (C++) 문제 및 풀이 문제) 백준 - BFS - 상근이의 여행 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 어떤 그래프로든 풀이가 가능하다. bfs가 제일 편해서 구현했다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9372_%EC%83%81%EA%B7%BC%EC%9D%B4%EC%9D%98%20%E.. 2021. 11. 7. [백준] 4485번 - 녹색 옷 입은 애가 젤다지? (C++) 문제 및 풀이 문제) 백준 - BFS - 녹색 옷 입은 애가 젤다지? https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net dist배열을 큰 수로 초기화한 후, BFS를 통해서 (n-1, n-1)까지 도달하는데 최소 비용을 구한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/4485_%EB%85%B9%EC%83%89%2.. 2021. 10. 21. [백준] 1707번 - 이분 그래프 (파이썬) 문제 및 풀이 문제) 백준 - 그래프 이론 (Graphs) - 이분 그래프 -> acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 그래프가 주어졌을 때, 집합을 둘로 나누어 한 집합에 속한 정점끼리는 인접하지 않게 분할하는 문제. 처음에 주어진 그래프가 당연히 연결 그래프일거라 생각해 약 2시간가량 맞왜틀(맞는데 왜 틀려)를 시전 했다. 연결 그래프가 아니어도 이분 그래프가 될 수 있음을 깨달았다. 그래프를 인접 리스트 형태로 선언하고, 각 노드가 어떤 집합에 포합 되.. 2021. 3. 12. [백준] 14502번 - 연구소 (파이썬) 문제 및 풀이 문제) 백준 - 너비 우선 탐색(BFS) - 연구소 - 14502번: 연구소 (acmicpc.net) 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 벽과 바이러스가 아닌 모든 지역(space)을 탐색해 벽의 후보(wall_candidates)를 골라 준다. combinations를 이용해 조합을 만들어주고 원본을 유지하기 위해 deepcopy를 이용해 복사 후 벽을 세워 bfs로 탐색해준다. 그 후 각 조합마다 안전 지역 개수의 최댓값을 구한다. 완전 탐색으로 접근하면 쉽게 풀리는 문제이지만 처음에 그리디하게 접근해서 헤.. 2021. 3. 3. 이전 1 2 3 다음 반응형
