백준/그래프83 백준 1414 c++ "블우이웃돕기" -PlusUltraCode- https://www.acmicpc.net/problem/1414 [필자 사고] 최소 스패닝 트리 알고리즘을 이용하여 푸는 문제이다. 알고리즘을 알고 문제를 풀면 쉽게 해결 하지만... 스패닝 트리라는걸 알기까지 과정이 힘들었따. 문제에서 핵심은 모든 컴퓨터가 랜선으로 서로서로 연결되어야 한다는 말이 있다. 이 부분을 Union 알고리즘을 이용하여 해결해 나갔다. 나머지 부분들은 랜선 길이를 기준으로 오름차순으로 정렬한뒤 스패팅 트리 알고리즘을 이용하여 해결했다.실수할 부분은 start지점하고 end지점이 같을 경우 제외해야 된다는 점이다. 아래는 코드 해설이다 1. Input 함수:먼저 Input 함수에서, 우리는 목표 노드에서 출발하여 네트워크를 스캔합니다. 여기서 각 노드는 출발점이며, 그 노드.. 2024. 9. 20. 백준 1389 c++ "케빈 베이컨의 6단계 법칙" -PlusUltraCode- https://www.acmicpc.net/problem/1389 [필자 사고]문제를 읽고 이해를 해보면 다음과 같다.1. 얼만큼의 친구들이 건너건너 있냐 => 모든 경로의 최단경로를 구한뒤 합을 구하면 케빈 베이컨법칙의 합이 만들어진다.2. 모든 경로를 구하기 위해 플로이드 와샬 알고리즘이 재격이다. 이 문제에서 조심해야 될 점은 가중치 값을 1로 설정하고 se만 설장할게 아니라 es도 양방향 선택해서 주입해야된다. 아래는 소스코드 해설이다. Input() 함수Input() 함수는 먼저 사용자로부터 노드의 수 N과 간선의 수 M을 입력받는다.그런 다음, 2차원 벡터 arr를 노드의 개수에 맞춰 초기화한다. 각 노드 간의 초기값은 매우 큰 수인 99999로 설정되며, 자기 자신으로의 경로(arr[i].. 2024. 9. 6. 백준 11404 c++ "플로이드" -PlusUltraCode- https://www.acmicpc.net/problem/11404 [필자 사고]1. 모든 경로의 최단 경로를 요구하는 문제이다.2. 특정한 시작점이 아니다. (다익스트라 x 벨만포드 x )플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있따.이 문제에서 조심해야 되는건 버스노선 입력할 때 똑같은 경로가 다른 가중치로 적힐 수 있따. 그래서 필자는 if(arr[s][e]>w) 일 경우 값을 갱신해주는 방법으로 함정을 피해갔다. 아래는 소스코드 해설이다. Input() 함수는 첫 번째로 사용자로부터 노드의 수 N과 간선의 수 M을 입력받는다. 이후, 2차원 배열 arr을 노드의 수에 맞게 초기화하는데, 각 배열의 값은 초기값으로 매우 큰 값인 999999999로 설정된다. 이는 도달 불가능한 경로.. 2024. 9. 6. 백준 1219 c++ "오민식의 고민" -PlusUltraCode- https://www.acmicpc.net/problem/1219 [필자 사고] 1. 무한히 돈을 벌 수 있다 2. 도착 도시를 도착했을 때 최대로 돈 벌수 있는 경우 => 벨만포드를 이용하면 특정 위치로부터 모든 경로를 탐색할 수 있게 된다. 이 문제에서 실수하기 쉬운 부분은 long 이다. 비용 관련 자료형은 long 으로 다 바꿔줘야 된다.또한 시작도시는 반드시 haveMoneys[start] = money[start] 를 해야된다.움직이지 않아도 현재 있는 도시니깐 초기화를 위와 같이 해줘야 된다. 아래는 코드 풀이다. Input() 함수노드의 수 N, 시작점 S, 목표점 E, 그리고 간선의 수 M을 입력받는다.money 벡터는 각 노드에서 얻을 수 있는 수익을 저장하며, haveMoneys.. 2024. 9. 5. 이전 1 2 3 4 5 6 7 ··· 21 다음
