본문 바로가기

Algorithm/Graph188

[파이썬] 백준 2887 : 행성터널 (플레5) [파이썬] 백준 2887 : 행성터널 (플레5) 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 0. 방향성 생각 지문만 읽으면 MST 문제임을 바로 알 수 있다. 이전 골드 문제와는 다르게 입력 크기가 10만이라서 모든 간선 정보를 받는 경우에는 n(n-1)/2 = 5*10^11이다. 특정 차원을 선택해서 위치별로 정렬시키고, 인접한 node끼리만 간선 정보에 추가해준다. (증명은 질문 게시판에) 1. 입력 from collections import defaultd.. 2023. 12. 16.
[파이썬] 백준 16933 : 벽 부수고 이동하기 3 (골드1) [파이썬] 백준 16933 : 벽 부수고 이동하기 3 (골드1) 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 방향성 생각 벽뿌2랑 동일한 문제. 다른 점이 있다면, 큐에 낮과 밤 정보를 넣어줘야 해서 메모리 관리가 조금 더 빡빡한 점. 전체코드 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() h,w,skill = map(int,input().split().. 2023. 12. 16.
[파이썬] 백준 14442 : 벽 부수고 이동하기 2 (골드3) [파이썬] 백준 14442 : 벽 부수고 이동하기 2 (골드3) 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 방향성 생각 간단한 최단거리 문제. 다익처럼 최단거리 갱신하는 경우에만 큐에 넣어서 시간 줄여주기 전체코드 from collections import deque import sys input = lambda : sys.stdin.readline().rstrip() h,w,skill = map(int,input().split()) arr = [list(in.. 2023. 12. 15.
[파이썬] 백준 1414 : 불우이웃돕기 (골드3) [파이썬] 백준 1414 : 불우이웃돕기 (골드3) 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 문제 풀이 0. 방향성 생각 MST 1. 입력 import sys input = lambda : sys.stdin.readline().rstrip() def cvt(x): nx = ord(x) if 65 2023. 12. 13.

티스토리툴바