다익스트라

2023년 8월 26일 알고리즘 문제풀이 문제 1 프로그래머스 전력망을 둘로 나누기 문제 링크 1차 시도 나의 생각 한 간선이 없어질 때마다 값을 모두 구한 후 가장 절대값이 작을 때를 찾았다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 from collections import deque def solution(n, wires): answer = n d = len(wires) for i in range(d): arr = deque() arr.append(0) graph = [[] for _ in range(n)] visited = [False for _ in range(n)] visited[0] = True for j in range(d): if j == i: continue else: a,b = wires[j] graph[a-1].append(b-1) graph[b-1].append(a-1) while arr: now = arr.popleft() for x in graph[now]: if not visited[x]: visited[x] = True arr.append(x) cnt = visited.count(True) cnt = abs(n-2*cnt) answer = min(answer,cnt) return answer 문제 2 프로그래머스 쿼드압축 후 개수 세기 문제 링크 ...

2023년 8월 24일 알고리즘 문제풀이 문제1 백준 1916 문제 링크 1차 시도 나의 생각 이전에 공부한 다익스트라로 풀면 되겠다고 생각했다. 출발지부터 각 도착지까지 비용을 표시하는 배열을 만들고 최소값으로 업데이트하였다. 그런데 이상하게 오답처리가 된다. 이유를 찾아봐야겠다. 결과 오답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 import sys from heapq import heappop, heappush n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) graph = [[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(m): s, a, c = map(int, sys.stdin.readline().split()) graph[s][a] = c start, arrive = map(int, sys.stdin.readline().split()) def search(x): cost = [10**9 for _ in range(n+1)] cost[x] = 0 arr = [] heappush(arr,[0, x]) while arr: price, now = heappop(arr) if price > cost[now]: continue for i in range(1, n+1): if not graph[now][i]: continue new_money = price + graph[now][i] if new_money < cost[i]: cost[i] = new_money heappush(arr,[new_money, i]) return cost ans = search(start) print(ans[arrive]) 2차 시도 나의 생각 원인을 찾아냈다. 나는 두 도시간의 비용을 인접행렬로 표현했다. 즉 행렬의 값이 두 도시의 이동 비용이다. 하지만 문제에서 각 도시 간의 노선이 하나라는 보장이 없다.. 그래서 두 도시간의 버스 비용이 중복해서 주어진다면 내 코드는 가장 마지막에 입력된 것만 나타내게 된다. 하지만 먼저 입력된 버스비용이 더 작다면? 내 코드에선 정답을 도출할 수 없었다. ...

2023년 8월 15일 알고리즘 문제풀이 문제 1 백준 1697 문제 링크 1차 시도 나의 생각 처음엔 재귀나 피보나치 등 여러 방법을 고민했다. 결국 다이나믹 프로그래밍으로 푸는게 적절하다고 생각했다. 맨처음 n에서 1초후 갈 수 있는 곳은 2n, n+1, n-1 이다. 이들을 큐에 저장하고 이들까지 도달하는데 걸린 시간도 같이 저장한다. 이 큐에서 하나씩 순회하며 2배한 좌표, +1, -1 한 좌표에 시간을 업데이트하고 큐에 다시 저장하는 것을 반복했다. 하지만 예시를 입력하면 올바른 정답이 나오지 않았다. 디버깅해봐야겠다. ...