본문 바로가기

Algorithm/Floyd Warshell

 (9)
(C++) - 백준(BOJ) 11562번 : 백양로 브레이크 https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 와샬 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 n,m,k 입력후 m만큼 u,v정점을 입력받은 것을 토대로 인접 그래프 adj를 형성해줍니다. 인접그래프의 초기값은 INF이며 갈 수 없는 경로는 1 갈 수 있다면 0으로 만들어줍니다. 📔 풀이과정 기존에 갈 수 있는 곳이라면 비용이 들지 않으나 인접해있지만 갈 수 없는 길을 가려면 길을 만들어줘야 하므로 1의 비용이 든다고 생각할 수..
(C++) - 백준(BOJ) 11265번 : 끝나지 않는 파티 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net floyd warshell문제였습니다. 📕 풀이방법 O(n^3)의 시간복잡도를 가지기 때문에 효율적이지는 않으나 n이 적절히 작을 경우 구현이 간편하기 때문에 자주 사용합니다. 📔 입력 및 초기화 인접그래프를 party라는 이 차원 배열에 입력받습니다. 이후 n, m만큼 적절히 입력받습니다. m만큼 각각 a,b,c를 입력했다면 party[a][b]는 a에서 b로..
(C++) - 백준(BOJ) 2458번 : 키 순서 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net floyd warshell 응용 문제였습니다. 풀이방법 간선을 i정점 - j정점으로 표현합니다. 1. 정점 u, v를 m만큼 입력받습니다. 이 정보는 이차원 배열 adj에 가는 경로가 있음을 표현하기 위해 1로 저장됩니다. 2. 입력 후에 바로 가는 경로외에 다른 정점을 거쳐 목적지 정점에 도착할 수 있는지 확인하며 정보를 저장합니다. i - k, k - j 가 연결이 되어있다면 i - j로도 갈 ..
(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 합승 택시 요금 https://programmers.co.kr/learn/courses/30/lessons/72413# 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr Floyd Warshell문제였습니다 풀이방법 1. 요금정보를 저장할 배열 cha..
(C++) - 백준(BOJ) 1976번 : 여행 가자 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net floyd warshell로 푼 문제였습니다. 풀이방법 1. i -> k로 갈 수 있고 k -> j로 갈 수 있다면 i -> j로도 갈 수 있기 때문에 입력받은 인접행렬을 갱신해줍니다. 2. 여행코스를 확인하면서 갈수 없으면 no, 강 수 있으면 yes를 출력해줍니다. Code #include using namespace std; int n,m,graph[201][201]; vectorcourse; int ma..
(C++) - 백준(BOJ) 11404번 : 플로이드 www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드 와샬문제였습니다. 풀이방법 1. 출발점과 도착점이 같은 입력이 여러번 주어질 수 있으므로 더 작은 가중치를 가진 도시를 인접행렬 dist배열에 저장해줍니다. 2. 플로이드 와샬 알고리즘을 수행합니다. i -> k 도시로 가는 비용 + k -> j 도시로 가는 비용 보다 i -> j로 가는 비용이 크다면 갱신해줍니다. 3. 각 도시로 가는 최소비용을 출력합니다. Code #include #define I..
(C++) - 프로그래머스(고득점 kit - 그래프) : 순위 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 플로이드 와샬 문제였습니다. 풀이방법 1. 누가 누구를 이겼는지에 대한 정보를 담을 2차원 배열 gameInfo라는 변수를 선언합니다. i선수가 j선수를 이겼다면 gameInfo[i][j] = 1이 됩니다. 2. 플로이드 와샬을 수행해서 누락된 승부 정보를 알아냅니다. 만약 i가 k를 이겼고 k가 j를 이겼다면 삼단논법에 의해 i는 j를 이긴것이 됩니다. 3. i가 j를 이겼거나 i가 j에게 패배했다면 그 개수를 세줍니다. 예를들어 2번 선수의 순위가 도출되려면 1,3,4,5번 선수..
(C++) - 백준(BOJ) 1058번 : 친구 www.acmicpc.net/problem/1058 1058번: 친구 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또다른 사람 B의 2-친구가 되기 위해선, 두 사람 www.acmicpc.net brute force로 친구 사이의 거리가 2이하인 간선을 세는 floyd warshell 문제였습니다. 풀이방법 1. 친구 i,j사이의 거리를 구합니다. i,j로 가는 거리보다 i -> k -> j로 가는 거리가 더 짧을 때 거리를 갱신하는 방식으로 모든 친구들에 적용합니다. 2. 구한 거리 배열 dist를 모두 순회하며 i의 모든 친구 사이의 거리가 2이하라면 세줍니다. 매번 i가 바뀔 때마다 최대값을 저장합니..

티스토리툴바