📁문제 풀이/🧩Baekjoon

[Python] 백준 1922 네트워크 연결 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제 해결 포인트 - 크루스칼 알고리즘 (최소 스패닝 트리 알고리즘) - 서로소 집합을 위한 find_parent, union_parent 함수 - edges : 간선 비용, 간선a, 간선b를 저장하여 오름차순으로 저장 - parent : 각 정점 별 집합 정보 저장 - 정렬된 edges 를 하나씩 방문하며 사이클이 발생하지 않는다면 간선 연결 - find_parent(a) != find_parent(b) 즉, 같은 집합에 속해있지 않다 ..

[Python] 백준 1647 도시 분할 계획 | 크루스칼 알고리즘

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 포인트 - 최소 스패닝 트리 문제 (크루스칼 알고리즘) - edges : 간선 비용을 오름차순으로 저장할 리스트 - parent : 서로소 집합 정보 저장할 리스트 - find_parent(x) : 서로 같은 집합에 속해있는지 확인하는 함수 - union_parent(a, b) : a, b 정점에 대해..

[Python] 백준 1197 최소 스패닝 트리

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 문제 해결 포인트 - 문제 이름에서 알 수 있듯 최소 스패닝 트리 알고리즘 문제입니다. - parent : 서로소 집합 개념에서 각 정점이 어느 집합에 속해있는지 정보를 저장 - edges : 간선의 정보를 저장하는 공간. 가장 작은 비용이 발생하는 간선부터 연결해나간다 - find_parent : 해당..

[Python] 백준 18405 경쟁적 전염 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 포인트 - 특정 위치를 중심으로 상하좌우 뻗어가므로 BFS가 적절 - 숫자가 작은 바이러스가 우선되어야 하므로 리스트로 받아 정렬 후 큐로 전환한다! - 큐에 값이 없어질 때까지 꺼내 상하좌우의 각 값이 다시 큐에 넣는 조건에 부합하는지 확인한다. - 큐에서 꺼낸 값의 시간이 S와 같다면 종료 - X-1 행 ..

[Python] 백준 14502 연구소 | BFS

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 포인트 - 0인 값의 모든 위치를 리스트 (blank)에 넣어서 cominations 모듈을 사용해 3개 위치 랜덤 추출(nCr) - 베이스가 되는 기존 정보에 해당 하는 3개의 위치를 1로 설정하고 check 함수 호출 - check 함수 ~ BFS를 위한 큐를 선언하여 값이 2인 위치를 넣는다. ~ 큐에 값을 하나씩 꺼내 해당 하는 위치에서 위, ..

[Python] 백준 4485 녹색 옷 입은 애가 젤다지? | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 문제 해결 포인트 - 다익스트라를 이용하여 각 위치별 (0, 0)에서 최소 비용을 계산 - dr, dc : 각 위치에서 아래, 위, 오른쪽, 왼쪽 위치를 방문 하기 위한 방향키 - graph : 각 위치 방문을 위해 필요한 비용 - distance : 각 위치에서 (0, 0)까지 가기위한 최소 비용, 초기는 무한수 작성 코드 imp..

[Python] 백준 1504 특정한 최단 경로 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 해결 포인트 - v1 -> v2 순서 또는 v2 -> v1 순서 각각의 거리를 구하여 작은 값을 출력한다. (2번의 다익스트라) - 경로가 없는 경우(결과 값이 INF보다 크거나 같은 경우) -1을 출력 자세한 내용은 코드 주석 참고 작성 코드 import sys import heapq input =..

[Python] 백준 13549 숨바꼭질 3 | 다익스트라

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 작성 코드 import heapq INF = int(1e9) N, K = map(int, input().split()) # 시작 위치, 도착 위치 distance = [INF]*100001 # 100001개의 떨어진 거리 def dijkstra(start): # 다익스트라 distance[start] = 0 # 시작..

[Python] 백준 1916 최소비용 구하기 | 다익스트라 | 시간초과

~목차~ 문제 문제 해결 포인트 작성 코드 문제 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 해결 포인트 - 받을 입력이 많으므로 sys.stdin.realine 을 사용한다. (시간 초과 해결) - 전형적인 다익스트라 문제 유형이다 - 우선순위 큐(최소힙)를 사용하여 최소 거리 노드를 선택 - distance : start 노드로부터 각 노드의 거리를 저장 (INF 로 초기화) - graph : 각 ..