그래프 (63) 썸네일형 리스트형 코드트리 빵 https://www.codetree.ai/training-field/frequent-problems/problems/codetree-mon-bread/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 시원하게 답이 나오지 않는다? 코드가 잘못 됐을 확률이 매우 높다! 새로운 방식을 생각해야한다. 제발 문제를 꼼꼼하게 읽어라 사람 이동 다하고 -1 처리 한다는 조건 사람이 움직이고 베이스 캠프 설정하는 조건 생각을 해보자. 베이스 캠프 기준으로도 bfs하고 사람을 기준으로도 bfs 하면 함수가 엄청.. 포탑 부수기 https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 1. 최단 거리이므로 BFS를 쓰자. split_damage를 위해서는 BFS의 경로를 이용! 경로를 저장하는 배열을 만들어 경로를 저장해가면서 BFS를 진행! 숨바꼭질 문제, DSLR 문제에서 풀었다. 우/하/좌/상의 우선순위대로 먼저 움직인 경로가 선택되므로 dx[], dy[]도 우/하/좌/상 순.. 다리 만들기 2 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 최소 스패닝 트리 문제이다. 일단 bfs로 섬을 마킹한 후, 섬에서 섬까지의 다리를 에지로 만들어 최소 스패닝 트리를 만들면 된다. 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49.. 최소 신장 트리 최소 신장 트리란 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 "최소"로 하는 트리. 특징 1. 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. 2. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N - 1개다. 1. 에지 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화 에지 리스트는 노드 변수 2개와 가중치 변수로 구성 사이클 처리를 위한 유니온 파인드 배열 배열의 인덱스를 해당 자리의 값으로 초기화 2. 그래프 데이터를 가중치 기준으로 정렬 에지 리스트에 담긴 그래프 데이터를 가중치 기준으로 오름차순 정렬 에지 리스트의 객체를 구조체로 표현하면 operator() 함수를 이용해 정렬을 수행 가능 3. 가중치가 낮은 에지부.. 벨만-포드 그래프에서 최단 거리를 구하는 알고리즘 시간 복잡도는 O(VE) 다익스트라는 O((V+E) log V) 다익스트라보다 느리다. 기능 : 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 탐색 에지 리스트를 이용한다 특징 : 음수 가중치 에지가 있어도 수행 가능 전채 그래프에서 음수 사이클의 존재 여부를 판단 가능 1. 에지 리스트로 그래프를 구현하고 최단 경로 배열 초기화 typedef tuple edge 최단 경로 배열은 출발 노드는 0, 나머지 노드는 ∞ 로 초기화 2. 모든 에지를 확인해 최단 거리 배열 업데이트하기 s = start, e = end, w= weight 업데이트 조건과 방법 D[s] != ∞ 이고 D[e] > D[s] + w 일 때 D[e] = D[s] + w로 업데이트. 반복 횟.. k번째 최단경로 찾기 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 $n$, $m$, $k$가 주어진다. ($1 ≤ n ≤ 1\,000$, $0 ≤ m ≤ 2\,000\,000$, $1 ≤ k ≤ 100$) $n$과 $m$은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이 www.acmicpc.net 도시의 개수 1000개 도로(에지)의 개수 2000000. 시간 제약 2초 다익스트라 알고리즘으로 접근하자. 근데, 최단 경로가 아닌 k번째 최단 경로 1. 최단 경로를 표현하는 배열을 우선순위 큐 배열로 두자. 이렇게 하면 최단 경로뿐 아니라 최단 경로 ~ k번쨰 최단경로까지 넣을 수 있다. 2. 방문 배열은 쓰지 않.. 다익스트라 기능 : 출발 노드와 모든 노드간의 최단 거리 탐색특징 : 에지는 모두 양수시간 복잡도 : O(ElogV) - V는 노드 수, E는 에지 수 1. 인접 리스트로 그래프 구현하기배열의 자료형은 (노드, 가중치)로 선언 2. 최단 거리 배열 초기화하기출발 노드는 0, 이외의 노드를 무한으로 초기화fill 함수는 O(N)이라서 무겁다..memset을 사용하자0x3f, 0x7f (제한이 더 크다면)보통은 0x3f 3. 값이 가장 작은 노드 고르기최단 거리 배열에서 현재 값이 가장 작은 노드를 고름 4. 최단 거리 배열 업데이트하기선택된 노드에 연결된 에지의 값으로 다른 노드의 값을 업데이트."선택 노드"의 최단 거리 배열의 값 + 에지 가중치 "연결 노드"의 최단 거리 배열의 값中 최소값 5. 3, 4 과정을 .. 퍼즐 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 처음에는 DFS로 접근을 했다. 재귀로 백트래킹을 시도했으 개같이 실패 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 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79.. 이전 1 2 3 4 5 6 ··· 8 다음