분류 전체보기121 [백준 10282번] 해킹 문제 풀이 '이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다' 라는 문구에서 방향이 있는 그래프임을 알 수 있다. 테스트 케이스의 크기만큼 반복하여, 다익스트라 알고리즘을 이용해 개수와 최대값을 구하면 감염된 컴퓨터의 개수와 모두 감염되는데 걸리는 시간을 구할 수 있다. import sys import heapq input = sys.stdin.readline INF = int(1e9) test_num = int(input()) def dijkstra(start): q = [] distance = [INF] * (n + 1) heapq.heappush(q, (0, start)) distance[start] = 0 while q: dist, no.. 2023. 8. 9. [백준 1238번] 파티 문제 풀이 먼저 간단한 다익스트라 구조를 이용하여 가는 거리와 오는 거리를 구해 최댓값을 구했는데, 입출력은 동일하나 시간 초과가 나왔다. 그래서, 힙을 이용하여 개선된 다익스트라 알고리즘을 사용하였더니 해결되었다. import sys import heapq input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m, x = map(int, input().split()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range(n +1)] # 모든 간선 정보를 입력 받기 for _ in range(m): a, b, c = map(int ,input().split()) # a번 노드에서 b번.. 2023. 8. 8. [백준 1504번] 특정한 최단 경로 문제 이 문제는 시작 노드에서 두개의 정점을 지나 마지막 노드까지 가는 경로의 최단 경로를 구하는 것으로, 시작노드(1) -> v1 -> v2 -> 마지막 노드(n)과 시작노드(1) -> v2 -> v1 -> 마지막 노드(n) 중 더 작은 값을 출력하면 된다. import sys input = sys.stdin.readline INF = int(1e9) # 노드의 개수, 간선의 개수 입력 받기 n, m = map(int, input().split()) # 각 노드에 연결 되어 있는 노드에 대한 정보를 담는 리스트 만들기 graph = [[] for i in range( n +1)] # 모든 간선 정보를 입력 받기 for _ in range(m): a, b, c = map(int ,input().split()).. 2023. 8. 7. [백준 6593번] 상범 빌딩 문제 풀이 입력 파트가 까다로워 문제는 복잡해보였으나 기본적인 BFS 최단 경로 문제였다. 3차원 배열을 입력받을때, 경로를 구할 같은 크기의 3차원 배열을 만들어 주었다. - 입력 파트 : 0 0 0을 입력하기 전까지 계속 최단 경로를 구해주어야 한다. a 배열은 3차원 배열의 값을 입력받고, d 배열은 해당 위치까지의 최단 거리를 저장, q는 bfs의 거리를 구하는데 사용한다. while True: l, r, c = map(int, input().split()) if l == 0 and r == 0 and c == 0: break a = [[[]*c for _ in range(r)] for _ in range(l)] d = [[[0]*c for _ in range(r)] for _ in range(l)] q =.. 2023. 8. 6. 이전 1 ··· 21 22 23 24 25 26 27 ··· 31 다음
