본문 바로가기
728x90

그래프64

[python] 백준 5214 환승 https://www.acmicpc.net/problem/5214 5214번: 환승 첫째 줄에 역의 수 N과 한 하이퍼튜브가 서로 연결하는 역의 개수 K, 하이퍼튜브의 개수 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ K, M ≤ 1000) 다음 M개 줄에는 하이퍼튜브의 정보가 한 줄에 하나씩 주어 www.acmicpc.net 문제 해결 BFS를 이용하면 쉽게 풀릴 것 같은 느낌이 든다. 문제는 하이퍼튜브로 두개의 역만 묶는 것이 아나리 두 개 이상의 역이 묶일 수 있다는 것이다. 그리고 메모리를 신경써야한다. BFS를 돌 때 역마다 방문했는지 체크하는 것이 아니라 어떤 하이퍼튜브를 이용했는가도 고려대상이 된다. 문제 해결 from collections import deque def bfs().. 2023. 6. 30.
[python] 백준 20056 마법사 상어와 파이어볼 https://www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제 해결 조건이 한 번에 이해하기 까다로웠다. 이동을 할 때 n행과 1행이 연결되어있어서 n행을 넘어가면 1행으로 텔레포트(?)가 가능하고 1열과 n열이 연결되어있어 n열이 넘어가면 1열로 텔레포트가 가능하다. 그리고 바닥 함수가 기호로 써져있어서 알지 못하면 처음에 이해하기 어려울 수 있다. https://ko.wikipedia.org/wiki/%EB%B.. 2023. 6. 22.
[python] 백준 9328 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제 해결 주어진 열쇠를 찾고 열쇠에 맞는 문을 열어 최대한 많은 문서를 찾는 문제 움직임을 보면 bfs를 이용하는 것이 편할 것 같다. 하지만 갔던 길을 또 갈 수 있으므로 갔던 길을 체크하는 visited를 성과가 있을 때마다 리셋을 시켜줘야한다. key의 유무를 dictionary를 통해 저장하면 좋을 것 같다. 한 번 얻은 문서는 다시 중복해서 먹을 수 없으므로 문서를 얻었으면 answer += 1을 .. 2023. 6. 22.
[python] 백준 19238 스타트 택시 https://www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 문제 해결 정해진 출발지에서 가장 가까이 있는 사람(같은 거리에 있으면 행이 작은 위치,열이 작인 위치 순으로 있는 사람)을 픽업한 다음 그 사람의 목적지에 도달시키면서 이동하면서 남은 연료를 출력하는 문제이다.(부족하면 -1) 따라서 출발지에서부터 각 위치의 최단 거리를 구한다음 가장 작은 사람을 픽업하러 간 후 그 위치에서 (정해진)목적지까지 거리를 계산.. 2023. 6. 22.
728x90