본문 바로가기

백준189

백준 11780 c++ "플로이드 2" -[PlusUltraCode] https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net [필자 사고] 이 문제는 다익스트라, 플로이드 둘다 사용해서 풀 수 있는 문제이다. 필자는 플로이드 와샬을 이용해서 풀었다. 주의할 점은 초기 배열에 값을 저장할때 Arr[i][k]= min(Arr[i][k],w); 이 작업을 반드시 해야 된다. 입력값이 기존보다 더 작은값이 들어올수도 있기 때문이다. 또한 parent배열의 경로를 찾을때는 아래코드가 핵심이니 기억해두자. while(st!=j.. 2024. 2. 28.
백준 1613 c++ "역사" -[PlusUltraCode] https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘을 이용하면 쉽게 해결할 수 있는 문제이다. 입력창을 보면 선후 관계 화살표로 주어 졌으므로 와샬 알고리즘을 사용후에는 후속 조취가 필요하다. 그 이유는 다음과 같다. 1->4 의 값이 자연수이고 4->1의 값이 무한대일때 1과4는 선후관계가 형성 되었따. 1->4를 보면 선후관계를 알 수 있지만 4->1을 보면 선후관계를 판별할 수 없기 때문이다. 이 .. 2024. 2. 28.
백준 1058 c++ "친구" -[PlusUltraCode] https://www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘이다. 플로이드 와샬 알고리즘의 중요한 특징이 있다. 문제에서 그래프로 주어 졌을때랑 2차원 배열로 주어 졌을때는 조금의 차이점이 있다. 먼저 그래프이다. 와샬 알고리즘 사용 후 1->4의 값이 자연수고 4->1 이 값이 무한대일 경우 1과 4의 관계가 형성 되었기 때문에 4->1의 값 또한 변경해줘야 된다. 반면에 배열로 주어졌을 경우 후속조취 없이 바로 와샬 알.. 2024. 2. 28.
백준 10159 c++ "저울" -[PlusUltraCode] https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net [필자 사고 ] 전형적인 플로이드 와샬을 이용하면 쉽게 해결할 수 있는 문제이다. 다만 알고리즘을 적용만 하면 답이 나오는 것이 아닌 이 문제의 특이한점은 순위가 결정 됬냐 안됬냐 하는 점이다. 만약 1->4 의 값이 자연수이고 4->1의 값은 무한대라고 했을 때 1과 4의 관계는 순위가 정해졌다고 말할 수 있따. 다만 플로이드 와샬 알고리즘을 적용하면 저런 형태로 나온다.. 2024. 2. 28.

티스토리툴바