[백준] 2251번 : 물통 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트
2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 1. 문제 설명 2. 풀이과정 지금까지 접해 봤던 그래프 데이터를 저장하고 저장한 자료구조를 이용하는 방식과 달리, 그래프 원리를 적용해 그래프를 역으로 그리는 방식으로 접근하는 문제이다. A, B, C의 특정 무게 상태를 1개의 노드로 가정하고, 조건에 따라 이 상태에서 변경할 수 있는 이후 무게 상태가 에지로 이어진 인접한 노드라고 생각하고 문제를 해결하면 된다. 처음에는 물통 A, B가 비어 있고, 물통 C는 꽉 차있는 상태이므로 해당 ..
2024. 2. 8.
[백준] 18352번 : 특정 거리의 도시 찾기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트
18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 1. 문제 설명 2. 풀이과정 해당 문제에서 모든 도로의 거리는 1이므로 가중치가 없는 인접 리스트로 그래프를 표현할 수 있다. 인접 리스트(adjacency list)는 파이썬의 리스트를 이용해 그래프를 표현한다. 도시의 개수가 최대 300,000개, 도로의 최대 크기가 1,000,000개이므로 BFS 탐색을 활용해 문제를 시간 복잡도 안에서 해결할 수 있다. 주어지는 도로의 정보를 입력받..
2024. 2. 2.
