전체 글 검색 결과
116 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 4485] 녹색 옷 입은 애가 젤다지? (python)

4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net BFS를 이용한다 맵의 정보를 받는 arr배열을 생성한다. 잃은 루피를 저장하는 arr1배열을 생성한다. 방문 여부를 확인하는 visited 배열을 생성한다. queue에는 [잃은 루피수, x좌표, y좌표]를 넣어준다. 상하좌우 이동하며 맵에 해당하는 좌표를 queue에 넣어준다. 마지막 값을 출력한다. import sys import heapq input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [-1,..

2021. 4. 19. 20:33
개발/알고리즘

[백준 1238] 파티 (python)

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 사용한다. 파티를 갔다가 와야하므로 정방향과 역방향 그래프 두개의 합을 계산해준다. 가는길 goarr, 오는길 comearr에 경로들을 저장한다. 가는데 걸리는 시간을 저장하는 time 배열을 생성한다. queue에 시작점을 넣어준다. 시작점에서 뻗을 수 있는 것들 중 저장되어 있는 것보다 더 작은 경로라면 update해주고 queue에 넣는다. 두 결과값을 더해서 큰값을 구해준다. import sys impo..

2021. 4. 19. 02:03
개발/알고리즘

[백준 10282] 해킹 (python)

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 다익스트라 알고리즘을 사용하자! arr에 의존 관계를 저장한다. time에는 감염되기 까지 걸리는 시간을 저장한다. (default = sys.maxsize) queue에 시작점 넣고 시작한다. 저장되어있는 감염시간(time[e])과 이전꺼에서 뻗어나가는 감염시간(w+v) 중 작은 것을 저장한다. time배열을 순회하며 sys.maxsize가 아닌 max 값과 개수를 구한다. import sys import heapq input = sys.stdin.readline ..

2021. 4. 19. 01:06
개발/알고리즘

[백준 1446] 지름길 (python)

1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 다익스트라 알고리즘을 이용한다. 지름길이 없을때 자기 자신을 default로 가지는 arr 배열을 생성한다. 0부터 목적지까지 돈다. 이전지점+1 이 더 작다면 update해준다. 지름길이 있다면 저장된 길이 (distance[타겟점])와 뻗어나간 길이 (w + distance[시작점]) 중 작은 것으로 update해준다. (지름길 시작지점이 D보다 작다고 해서 arr 배열을 range(D+1)로 했는데 Indexerror가 난다. 왜나는 걸까?) i..

2021. 4. 18. 23:01
개발/알고리즘

[백준 1197] 최소 스패닝 트리 (python)

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리(minimum spanning tree​) 전체 요소들을 연결할 때 사용한다. Kruskal 알고리즘, Prim 알고리즘이 있다. Kruskal 간선들을 정렬 간선이 잇는 두 정점의 root를 찾는다. 다르다면 하나의 root를 바꾸어 연결 시켜준다. Prim 임의의 정점을 선택 해당 정점에서 갈 수 있는 간선을 minheap에 넣는다. 최소값을 뽑아 해당 정점을 방문 안했다면 선택한다. Kruska..

2021. 4. 18. 02:48
개발/알고리즘

[백준 13549] 숨바꼭질 3 (python)

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net BFS를 사용! 두배한 것은 0초만에 된다는 것이 포인트! 방문 여부 Check 배열과 담을 queue 배열을 생성한다 2배는 0초만에 이루어지므로 먼저 계산되어야하므로 queue 앞으로 넣어준다. +1과 -1 queue 뒤로 넣어준다. import sys from collections import deque input = sys.stdin.readline N, K = map(int, input().split()) check = ..

2021. 4. 13. 17:07