본문 바로가기
728x90

그래프64

[python] 백준 2251 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 문제 해결 하노이탑 같은 문제 느낌이 들었다. x+y+z = c (c는 상수)이므로 x,y를 변수로 두면 z는 알아서 구해진다. bfs문제로 푸는 것이 좋을 듯 싶다. CODE from collections import deque sender = [0, 0, 1, 1, 2, 2] receiver = [1, 2, 0, 2, 0, 1] limit = list(map(int, inp.. 2023. 2. 28.
[python] 백준 1525 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 문제 해결 표에 숫자를 넣고 빈 곳(0)을 이용해 이동하는 문제 이동 방법은 동서남북이므로 move =[(-1,0), (1,0), (0,-1), (0,1)] 4가지가 있다. 위의 조건과 최소 이동 번수를 구하는 것이므로 아무래도 bfs가 좋다. 그런데 어떻게 풀어야하지?? (ㅜㅜ) 답은 리스트가 아니라 문자열 이용! 1 2 3 4 5 6 7 8 9 위 표는 "123456789" 문자열로 변환 시킬 수 있다! 그리고 n 위치는 (n//3, n%3) 으로 좌표를 만들 수 있다... 2023. 2. 28.
[python] 백준 18352 특정 거리의 도시 찾기 https://www.acmicpc.net/problem/18352 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 문제 해결 특정 지점까지 가는데 최소 거리가 k인 점을 찾는 문제 (DFS,BFS 다 되지만 거리가 정해져있으므로 BFS로 너비로 찾는 것이 좋다!) 양방향 도로가 아니라는 것에 주의하자! CODE import sys from collections import deque input = sys.stdin.readline n, .. 2023. 2. 26.
[python] 백준 2250 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 문제해결 중위 순회(incoder)(왼쪽 하위트리 → 루트 → 오른쪽 하위 트리 방향) 방식으로 보며 되며 그 순서를 x축에 표현한 것으로서 num이라는 변수로 표현하였으며 그 때의 깊이(level)을 index로 하여 row리스트에 저장을 한다.(append) row리스트에 모든 로드를 저장한 후 level=1부터 level=n까지 각 레벨에서 최대 x축(num)값을 가진 노드.. 2023. 2. 1.
728x90