본문 바로가기
728x90

알고리즘339

[python] 백준 2159 케익 배달 https://www.acmicpc.net/problem/2159 2159번: 케익 배달 첫째 줄에 N이 주어지고 둘째 줄에는 선아가 일하는 레스토랑의 위치가, 셋째 줄부터는 N명의 위치가 X와 Y로 주어진다. 두 좌표 사이에는 공백이 하나 이상 있다. (1 ≤ N, X, Y ≤ 100,000) www.acmicpc.net 문제 해결 케익을 받는 순서는 정해져 있다. 케익을 받을 수 있는 위치는 모두 4가지이다. 그래서 출발점-도착점에 따른 최소거리를 각각 구해야한다. 받는 위치가 다르면 다음 순서에 영향을 줄 수 있기 때문 이를 구현하기 위해 가장 좋은 것은 DP이다. dist[i][j] 는 i번째 사람 케익을 받을 때 동(j=0),서(j=1),남(j=2),북(j=3),(아래 코드는 +중앙(j=4))에.. 2023. 7. 7.
[python] 백준 5567 결혼식 https://www.acmicpc.net/problem/5567 5567번: 결혼식 예제 1의 경우 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2, 3, 4 3명의 친구를 결혼식에 초대 www.acmicpc.net 문제 해결 그래프의 전형적인 문제 처음 시작 노드 1에서 한 번 다른 노드로 이동할 때마다 횟수 변수 cnt를 1씩 증가시킬 때 cnt가 2 이하인 노드들의 개수를 구하는 문제 que를 만든 후 연결 된 노드로 이동하면서 cnt가 2이상이면 더 뻗어 나갈 수 없으므로 멈추고 이동한 노드의 cnt가 2보다 작으면 que에 넣어 다른 노드로 또 이동한다. CODE from collect.. 2023. 7. 4.
[python] 백준 11967 불켜기 https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 문제 해결 BFS로 방을 움직이면서 불을 켜는 문제 첫 번째 문제는 A방에서 B방의 불을 켤 수 있다는 것이다.(이는 문제에서 주어진다.) 그러면 이동하면서 A방에서 킬 수 있는 불은 모두 켜야한다. ( (i,j)위치의 방에 불이 켜지면 값이 0→1로 바뀌는 것으로 구현) 두 번째 문제는 조건부로 동,서,남,북 중 방에 불이 켜져있는 방향으로만.. 2023. 7. 3.
[python] 백준 5214 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 문제 해결 BFS를 이용하면 쉽게 풀릴 것 같은 느낌이 든다. 문제는 하이퍼튜브로 두개의 역만 묶는 것이 아나리 두 개 이상의 역이 묶일 수 있다는 것이다. 그리고 메모리를 신경써야한다. BFS를 돌 때 역마다 방문했는지 체크하는 것이 아니라 어떤 하이퍼튜브를 이용했는가도 고려대상이 된다. 문제 해결 from collections import deque def bfs().. 2023. 6. 30.
728x90