그래프

[python] 프로그래머스 - 동굴 탐험 (2020 카카오 인턴십)

문제 해결 1. 그래프 문제 2. 주어진 path 로 인접리스트를 만든다. 3. 주어진 order 로 딕셔너리를 만든다. (1) a 를 방문해야 b 를 방문할 수 있다. (2) a를 키, b를 밸류로 하는 딕셔너리를 만든다 | a를 방문했을 때 b를 방문할 수 있다 라는 것을 찾기 위해| (3) b를 키, a를 밸류로 하는 딕셔너리를 만든다 | b를 방문하려고 하는데 a를 이미 방문했는지 알아보기 위해| (4) a가 0인 경우(선행 조건이 0번방을 방문하는 것) 이므로 값을 0으로 해준다.) (5) b가 0인 경우(0번방을 방문하기 위해 다른 방을 방문하고 와야 하므로 처음부터 방에 들어가지 못한다.) 4. visited 배열(0과 1)을 만든다. 방문했는지 안했는지 알아보기 위해 5. 큐를 만들어 BF..

[python] SWEA - 1251. 하나로 / 1486. 장훈이의 높은 선반

1. 하나로 문제 해결 1. 프림 + 힙큐 2. 인접리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. key 리스트를 최솟값으로 갱신해가며 결과를 더해준다. 🔨 인접 행렬로 하다가 몇시간 날린 것 같다. 역시 난 인접리스트를 쓰는게 편하다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) x_location = list(map(int, input().split())) y_location = list(map(int, input().split())) tax = float(input()) # 인접 리스트 adj = {i: [] for i in range(n)} for s in range(n): fo..

[python] SWEA - 1249. 보급로 / 5521. 상원이의 생일파티

1. 보급로 문제 해결 1. 다익스트라 알고리즘 + 힙큐 2. 가중치 리스트와 방문 리스트를 만들어 준다. 3. 힙큐를 이용해 가중치가 가장 낮은 점을 선택하고 4. 주변을 탐색하여 최소 가중치를 선택해 가중치를 점점 누적해 나아간다. 소스 코드 import heapq for tc in range(1, 1+int(input())): n = int(input()) maps = [list(map(int, list(input()))) for _ in range(n)] # dist: 가중치를 누적한 리스트, visit: 선택했는지 안했는지 dist = [[float('inf')]*n for _ in range(n)] visit = [[False]*n for _ in range(n)] dx, dy = [-1, 1..

[python] 백준 - 1753. 최단경로

문제 해결 1. 방향이 있는 그래프에서 최단거리를 구하는 문제 | 보통 다익스트라 알고리즘을 사용한다. 2. 인접리스트, 가중치 배열, 힙큐를 준비한다. (1) 인접행렬보다 인접리스트가 조금 더 빠르다(?) (2) 가중치 배열: 인덱스 번호에 도착할 때의 가중치를 항상 최솟값으로 업데이트 해준다. (3) 힙큐는 항상 최솟값을 리턴해준다. 3. ex)a - c 와 a- c 로 갈 때의 가중치를 항상 비교하여 최솟값을 넣어줘야 한다. -> selected배열(출발했었는지 확인)을 만들어서 했는데 어짜피 단방향이라 필요가 없었다. python으로 제출 시 시간초과가 나서 pypy로 제출했더니 통과 했다. python으로 통과한 사람과의 코드를 비교해봤는데 차이가없었다..... 후😭 왜때문인지 모르겠다. 소스 ..

[python] 백준 - 1922. 네트워크 연결

문제 해결 1. 오늘 배운 최소 신장 트리(MST)를 사용하는 그래프 문제다. ( + heapq 모듈 사용 ) 💨 그래프에서 사이클을 제거하고 모든 노드를 포함하는 트리를 구성할 때, 가중치의 합이 최소가 되도록 만든 경우를 최소신장트리라고 한다. (1) 먼저 간선과 가중치를 인접리스트로 만든다. (2) key, mst, pq | 최소 가중치를 갱신하는 배열, 방문 배열, 힙큐( 최소값을 뽑는 모듈 ) 2. 시작점( 노드중 아무거나 )을 힙큐에 넣어주고 시작 - 이 문제에서는 모든 노드를 연결할 수 있다. (1) 힙큐 안에서 가중치가 가장 낮은 정점을 pop (2) 방문했는지 확인 | 이미 방문을 했다면 continue 를 통해 힙큐에서 다시 뽑고, 아니라면 True로 바꿔주고 가중치를 결과에 더해준다...

[python] 백준 - 2644. 촌수계산

문제 해결 1. 노드간의 최단거리를 구하는 그래프에 관한 기본적인 문제이다. 2. 먼저 주어진 부모자식들 간의 관계를 가지고 인접리스트를 만든다. 3. visit 배열을 만들어 방문 여부를 가지고 DFS 재귀함수를 진행한다. (1) 현재 노드에 인접한 노드를 for문을 통해 뽑아주고, (2) 만약 인접한 노드가 아직 방문하지 않은 상태라면, 그 노드로 이동 - 재귀 (3) 이동한 노드가 구해야하는 노드라면 방문한 노드들의 갯수를 세어주고 결론을 도출. -> 쉬운 문제라고 생각했는데 한참동안 '틀렸습니다'를 얻었다. 이번에도 역시 이웃님의 도움을 받았다. `촌수관계를 나타내지 못하면 -1을 출력해라`....... 문제를 잘 읽어보는 습관을 들여야겠다. 소스 코드 n = int(input()) a, b = ..