알고리즘/백준
-
[백준] 1162 도로포장 파이썬알고리즘/백준 2021. 2. 19. 18:41
문제 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 풀이 1. 서울에서 시작하여 포천까지 최소 시간이 걸리도록 해야합니다. 2. 도시별로 최소 시간을 구하기 위해서 다익스트라 알고리즘을 구현합니다. 3. 주의할 점은 K개를 사용해서 거리를 포장하면 시간이 0이 되기 때문에 이 부분을 구현해야 합니다. 4. 구현하는 방법은 도시별의 최소 시간과 도시별 방문 유무 리스트를 2차원(N * K)으로 늘려주면 됩니다. 포천에서 1 ~ K번 포장했을 때의 최단시간을 구해주고 그중 최..
-
[백준] 1068번 트리 파이썬알고리즘/백준 2020. 12. 30. 23:57
문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 1. 노드 클래스와 트리 클래스를 기본적으로 틀을 짜줍니다. 2. 트리 클래스에 깊이 우선 탐색 알고리즘을 이용하여 현재 노드에서 자식노드가 지워줄 노드가 같다면 해당 자식을 리스트에서 제거합니다. 3. 이때 루트 노드와 지워줄 노드가 같다면 트리의 root를 none으로 바꿔주고 예외 처리로 0을 출력해줍니다. ( 루트 노드부터 지운다면 트리 전체가 없어진다는 뜻) 4. 그후 다시 트리 전체를 깊이 우선 탐색하여 현재의 노드가 자식이 없을 경우..
-
[백준] 14502번 연구소 파이썬알고리즘/백준 2020. 12. 29. 20:22
문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 1. 우선 벽 3개를 무조건 세워야 하기 떄문에 완전탐색으로 케이스마다 벽 3개를 세워줍니다. 2. 그다음에 너비 우선 탐색으로 케이스 마다의 안전 영역 크기를 구합니다. 3. 케이스 마다의 안전 영역 크기중에 가장 큰 수를 리턴합니다. 코드 from copy import deepcopy from collections import deque from itertools import combinations dxy = [[0, 1], [0, -1], [1, 0], [-1..