Algorithm/Graph188 [파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5) [파이썬] 백준 15806 : 영우의 기숙사 청소 (플레5) 15806번: 영우의 기숙사 청소 통학이 너무나도 하기 싫었던 영우는 결국 학교의 기숙사에 들어갔다. 통학의 고통에서 해방된 기쁨도 잠시, 학교 기숙사에서는 일정 기간마다 청소 검사를 한다는 사실을 알게 되었다. 청소 검 www.acmicpc.net 문제 풀이 0. 방향성 생각 그림2의 (a) (b)의 시작 곰팡이 위치를 보면 서로 교차해서 나타나는 것을 확인할 수 있다. 홀수일에 피는 곰팡이, 짝수초에 피는 곰팡이, 항상 피어있는 곰팡이로 구분한다. 예제 1번의 테케를 보면 곰팡이가 중앙에서 피어서 증식하지 못하는 경우도 생긴다. 입력에 추가하기 전, n = 1,2거나 n=3의 중심처럼 곰팡이가 증식하지 못하는 엣지케이스 잡아내기 1. 입력 .. 2023. 12. 23. [파이썬] 백준 23034 : 조별과제 멈춰 (플레5) [파이썬] 백준 23034 : 조별과제 멈춰 (플레5) 23034번: 조별과제 멈춰! 교수님이 시험 기간에 조별 과제를 준비하셨다...! 가톨릭대학교의 조교 아리는 N명의 학생을 2개의 조로 구성하여 과제 공지를 하려 한다. 이때, 구성된 각 조의 인원은 1명 이상이어야 한다. 각 www.acmicpc.net 문제 풀이 0. 방향성 생각 2개의 집합으로 분리 + 최소비용으로 간선 잇기 = 크루스칼 두 간선 사이 연결 끊기 : a 노드부터 b 노드까지 간선 중 최대값을 끊으면 최소 비용으로 두 집합 분리 가능 a,b가 10000개 이상 주어지니, 시간초과 해결을 위해서 a와b 사이 최대값을 구하는 list를 만들어준다. 1. 입력 from collections import deque import sys i.. 2023. 12. 22. [파이썬] 백준 1944 : 복제 로봇 (골드1) [파이썬] 백준 1944 : 복제 로봇 (골드1) 1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 문제 풀이 0. 방향성 생각 읽어보면 모든 노드를 방문하는데 최소 비용을 쓴다. 각 노드에서 복제가 일어나서 각 노드별로 최단거리를 먼저 구해줘야함. 여기서 S=K라고 생각해도 좋다. 역할동일 이동 시 간선 비용이 같으니 BFS를 돌려서 각 노드별 거리를 구해준다. 모든 노드를 방문하면서, 간선 길이의 합이 최소가 되는 -> MST 문제임을 확인할 수 있다. 1. 입력 from co.. 2023. 12. 19. [파이썬] 백준 1194: 달이 차오른다, 가자. (골드1) [파이썬] 백준 1194: 달이 차오른다, 가자. (골드1) 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 문제 풀이 0. 방향성 생각 열쇠를 먹은 유무에 따라 문을 열수있는지 여부가 정해진다. 2D 배열이 2500, 열쇠가 6개이므로 2500*64 정도면 충분히 비트마스킹으로 가능 3D visit 배열을 만들어서 BFS로 진행 1. 입력 from collections import deque,defaultdict as dd import sys input = lambda : sy.. 2023. 12. 19. 이전 1 ··· 25 26 27 28 29 30 31 ··· 47 다음
