본문 바로가기

백준154

백준 1507 c++ "궁금한 민호" -[PlusUltraCode] https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net [필자 사고] 플로이드 와샬 알고리즘이 이미 적용된 상태로 입력값으로 들어온 문제다. 이 문제를 해결하려면 3가지 정도를 이해해야 된다. 1. s->e 가는 경로보다 s->k + k->e 경로의 합이 더 작을경우 문제가 생긴다. 그 이유는 이미 문제에서 입력값이 플로이드 와샬이 적용된 최단 거리만 주어지는데 저 식이 성립한다면 최단거리가 더 존재한다는 의미이다. 문제 자체가 모순이 되기 때문에.. 2024. 2. 29.
백준 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.

티스토리툴바