분류 전체보기

[백준1238&파이썬] 다익스트라를 여러번 사용해서 최장 경로를 얻어보자

# 문제 백준 1238 파티 파이썬 풀이 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 코드 ''' - 오고 가야함, X까지 오는건 각각 구하고, X에서 다시 원래 지점까지 가는 방법은 X로 다익스트라 한번만 돌리면 될듯 - total_distance를 하나 만든다 - total_distance는 X에서 N까지의 모든 경로를 미리 구해놓는다 - 이후 N -> X로 가는 최단거리의 값을 구해서 다익스트라를 사용해서 해당 경로에 더해준다. ''' import sys from c..

[백준11779&파이썬] 다익스트라에서 경로 추적이 필요할땐 route배열을 만들어 활용하자

# 문제 백준 11779 파이썬 최소비용 구하기 풀이 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net # 코드 ''' - 경로를 구해야 하기 때문에, 경로가 확정되면 이전에 어디서 왔는지를 distance에 함께 저장하던지, 경로 배열을 만들어서 사용해야 함 - 최소 경로로 가는 법은 한가지 이상일 수 있음, 백준 예제는 하나만 나와서 괜히 뭐 틀린 줄 알고 찾았네.. ''' import sys import heapq from collections import defaultdic..

[백준1753&파이썬] 다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구할 수 있다.

# 문제 백준 1753 최단경로 파이썬 풀이 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net # 코드 ''' 1. 다익스트라는 시작정점으로부터 모든 정점까지의 최단거리를 구할 수 있다 2. 간선(Edge)의 값이 0 이상의 양수일때 정상 작동한다. - 최단 거리 테이블 초기화( 시작 노드 0, 나머지 inf ) - https://www.acmicpc.net/board/view/82405 그래프 초기화 관련 - 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에..

[백준1707&파이썬] BFS를 활용하여 이분 그래프를 판별하는 방법

# 문제 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net # 코드 import sys from collections import defaultdict from collections import deque RED = 1 BLUE = -1 def solve(): V, E = map(int, sys.stdin.readline().split()) # V 정점의 개수, E 간선의 개수 graph = defaultdict(list) visit = [0] * (V + 1) # 0 == 방문X , 1 == RED , -1 ..

[백준2251&파이썬] BFS는 가지치기로 경우의 수를 구하기 적합하며 방문처리의 방법을 생각해보자

# 문제 백준 2251 물통 파이썬 풀이 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net # 코드 import copy import sys from collections import deque A, B, C = map(int, sys.stdin.readline().split()) max_size = (A, B, C) result = set() # visit를 어떻게 처리할 것인가 ? ## 병이 똑같은 상태가 된다면 visit로 처리하는게 맞을듯 하다. ## 3차원 배열을 쓰는건 너무 메모리..

[백준4803&파이썬] BFS를 활용하여 사이클을 찾아 트리여부를 확인하자

# 문제 백준 4803 트리 파이썬 풀이 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net # 코드 import sys from collections import deque from collections import defaultdict def solve(n,m) : ddict = defaultdict(list) for _ in range(m) : a,b = map(int,sys.stdin.readline().split()) ddict[a].append(b) ddict[b].append(a) ..