본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[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.
[python] 백준 2283 구간 자르기 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 해결 리스트 인덱스를 x좌표로 하여 막대의 좌표 ( ex: (3,7)이면 vertical[3:7]에 +1씩 더해서 길이를 측정할 수 있도록 한다.)로 나타낸다. 원하는 만큼의 길이(k)가 안나오면 끝점(r)를 1씩 높여서 해당되는 길이만큼 증가시키고 그보다 크게 나오면 시작점(l)를 1씩 높여서 해당되는 길이만큼 줄이면서 원하는 값이 나오는.. 2023. 6. 26.
728x90