알고리즘(python) 검색 결과
179 개의 검색 결과가 있습니다.
알고리즘(python)/탐색

[Python]최단경로 백준 1504

문제 https://www.acmicpc.net/problem/1504 다익스트라를 여러번 이용해 찾는 문제이다.양방향이라는 점에 주의 하여야 입력을 받아야 하고 반드시 거쳐야하는 두점중 하나가 N번 정점일수 있다는 것도 생각해야한다.이 두가지 를 고려하지 않아 몇번 틀렸다. 12345678910111213141516171819202122232425262728293031323334353637383940414243import sysimport heapqINF=sys.maxsize def Dijkstra(start): q=[] heapq.heappush(q,[0,start]) result=[INF for _ in range(V+1)] result[start]=0#둘중하나가 도착점일 경우를 생각해서 자신으로 ..

2020. 2. 19. 20:06
알고리즘(python)/탐색

[Python]최단경로 백준 1753

문제 https://www.acmicpc.net/problem/1753 다익스트라 알고리즘을 사용하여야 한다.위키를 통해 다익스트라 알고리즘을 살펴보자.다익스트라 알고리즘이란 도로 교통망 같은 곳에서 나타날 수 있는 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘이다.원래 알고리즘은 두 꼭짓점 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 꼭짓점을 "소스" 꼭짓점으로 고정하고 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.최단 경로 알고리즘은 네트워크 라우팅 프로토콜에서 널리 이용되며, 특히 IS-IS (Intermediate System to Intermediate System)와 OSPF(Open Shortest Path First..

2020. 2. 17. 23:59
알고리즘(python)/탐색

[Python]DFS와BFS 백준 2206

문제 https://www.acmicpc.net/problem/2206 이전 미로찾기와 다른점은 벽을 한번 뚫었을때의 경우도 생각해준다.벽을 뚫지 않았을때와 한번 뚫었을때를 따로 저장해 준다.이전 미로찾기 코드에서 벽에 대한 코드만 추가해보자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849import sysfrom collections import deque def find_maze(start_row,start_colume,N,M):#bfs를 통해 찾기 q=deque() q.append([start_row,start_colume,0]) wallcheck[start_row][start_colum..

2020. 2. 15. 23:02
알고리즘(python)/탐색

[Python]DFS와BFS 백준 1697

문제 https://www.acmicpc.net/problem/1697 이 문제 역시 BFS를 사용하여 풀수있다.정답률과 다르게 매우 쉬운문제이다.DP문제와 유사해보이지만 이전값들을 사용하는 문제가 아니다. 계속 이동해가며 찾아가면된다. 100000을 넘어서 이동한값들은 생각할 필요가없다. 1234567891011121314151617181920212223242526from collections import deque N,K=map(int,input().split())check=[0 for _ in range(100001)] q=deque()q.append(N)check[N]=1while q: x=q.popleft() if x==K: time=check[x]-1 break if x+1=0 and chec..

2020. 2. 15. 13:12
알고리즘(python)/탐색

[Python]DFS와BFS 백준 7569

문제 https://www.acmicpc.net/problem/7569 이전 토마토 문제와 거의 다르지 않다.3차원배열을 만들어 높이도 넣어주면된다.코드는 거의 동일하고 높이를 처리하는 부분만 추가하였다. 123456789101112131415161718192021222324252627282930313233M,N,H=map(int,sys.stdin.readline().split())tomatos=[]#for _ in range(H): tomato=[] for _ in range(N): tmp=list(map(int,sys.stdin.readline().split())) tomato.append(tmp) tomatos.append(tomato) ripen=[]#익은토마토unripen=0empty=0for ..

2020. 2. 15. 11:14
알고리즘(python)/탐색

[Python]DFS와BFS 백준 7576

문제 https://www.acmicpc.net/problem/7576 이 문제도 bfs를 통해 풀수있다.처음에 익은 토마토를 모두 넣어주면된다.큐가 빌때까지 반복하고 모든 토마토가 익어있을때와 모두 익지 못하는상황도 잘처리해준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061import sysfrom collections import deque def box(ripens,N,M,unripen,empty): if len(ripens)==N*M-empty:#처음부터 모든 토마토가 익어있다면 return 0 q=deque() for ripen in ri..

2020. 2. 14. 23:39