[BOJ알고리즘, C++]#1058_친구, 최단 경로, 길 찾기, 플로이드-워셜

2024. 5. 21. 16:43· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 플로이드-워셜
  4. 2. 최단 경로를 찾고, 두 정점 쌍에 대하여 최단 경로 값이 2 이하인 쌍을 찾자!
  5. #3. 코드

 

#1. 문제

https://www.acmicpc.net/problem/1058

 


 

#2. 풀이

 

1. 플로이드-워셜

 

[알고리즘]#2_길 찾기 알고리즘

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입..

webddevys.tistory.com

플로이드-워셜 알고리즘은 음수 가중치를 포함하는 그래프 자료구조에서 "전체-쌍" 최단 경로를 구하는 길 찾기 알고리즘입니다. 플로이드-워셜 알고리즘은 "음수 가중치", "사이클 여부", 그리고 "경유 정점 혹은 경유 정점을 통한 새로운 경로" 개념에 적용하기에 적절한 알고리즘입니다. 플로이드-워셜 알고리즘의 최악 시간 복잡도는 O(n³)입니다.

 

2. 최단 경로를 찾고, 두 정점 쌍에 대하여 최단 경로 값이 2 이하인 쌍을 찾자!

  1. 먼저, int graph [MAX][MAX] 형식의 그래프 자료구조(인접 행렬)를 구성해 줍니다.
  2. 그리고, 플로이드 워셜을 수행합니다. 3단 중첩문을 통해 시작점과 도착점의 최단 경로 값을 업데이트해줍니다.
  3. 마지막으로, 두 정점 쌍에 대하여 최단 경로 값이 2 이하인 쌍을 찾아 카운트해 줍니다.

 


 

#3. 코드

/*
    @문제 : 2- 친구가 최대가 되는 수 찾기
    @설명
        1. 플로이드 워셜
        2. [i][i] = 0, [i][j] = 1, [i][그 외] = INT_MAX
        * 중요 : 플로이드-워셜은 U-V 경로와 U-K + K-V 경로의 비교를 통해 최단 경로를 업데이트합니다.
                 관계 경로가 3~INT_MAX일지도 모를 두 사람이 각각 친구 관계에 있는 제 3자를 통해 관계 경로가 단축될 수 있습니다!
                 최대 친구 수를 찾는 것은 뒤로 미루고, 어느 두 사람 사이의 '최소 관계 경로'를 찾는다고 생각하자!
                 
*/

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

#define MAX 51

int N;
int graph[MAX][MAX];
int res[MAX] = {0,};
int ans = INT_MIN;

void Floyd()
{
    // #1. 3단 for문 : u -> k 가 친구 + k -> v가 친구이며, u->v 보다 u->k + k->v 경로 관계가 짧다면 업데이트!
    for(int k=1; k<=N; ++k)
    {
        for(int u=1; u<=N; ++u)
        {
            for(int v=1; v<=N; ++v)
            {
                if(graph[u][k] != INT_MAX && graph[k][v] != INT_MAX
                && graph[u][v] > graph[u][k] + graph[k][v])
                {
                    graph[u][v] = graph[u][k] + graph[k][v];
                }
            }
        }
    }

    // #2. 각 사람에 대하여, 관계 경로가 2이하인 친구들을 카운트하고, 최대 값을 찾는다.
    for(int u=1; u<=N; ++u)
    {
        int cnt = 0;
        for(int v=1; v<=N; ++v)
        {
            if(u != v && graph[u][v] <= 2)
            {
                cnt++;
            }
        }
        ans = max(ans, cnt);
    }
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    // 그래프 구성
    for(int i=1; i<=N; ++i)
    {
        string isFriend;
        cin >> isFriend;

        for(int j=0; j<=isFriend.length()-1; ++j)
        {
            // 친구여부 체크
            if(isFriend[j] == 'N')
            {
                if(i == j+1) graph[i][j+1] = 0;
                else graph[i][j+1] = INT_MAX;
            }
            else{
                graph[i][j+1] = 1;
            }            
        }
    }

    // 플로이드 워셜
    Floyd();
    
    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#15900_나무 탈출, DFS, 깊이 우선 탐색  (0) 2024.05.21
[BOJ알고리즘, C++]#13511_트리와 쿼리2, 트리, LCA, 노드 사이 거리  (0) 2024.05.21
[BOJ알고리즘, C++]#1949_우수마을, 트리 DP  (0) 2024.05.15
[BOJ알고리즘, C++]#10159_저울, 최단 경로, 길 찾기, 플로이드-워셜  (0) 2024.05.15
[BOJ알고리즘, C++]#15654_N과M(5), 백트래킹, 순열 백트래킹  (0) 2024.05.15
  1. #1. 문제
  2. #2. 풀이
  3. 1. 플로이드-워셜
  4. 2. 최단 경로를 찾고, 두 정점 쌍에 대하여 최단 경로 값이 2 이하인 쌍을 찾자!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#15900_나무 탈출, DFS, 깊이 우선 탐색
  • [BOJ알고리즘, C++]#13511_트리와 쿼리2, 트리, LCA, 노드 사이 거리
  • [BOJ알고리즘, C++]#1949_우수마을, 트리 DP
  • [BOJ알고리즘, C++]#10159_저울, 최단 경로, 길 찾기, 플로이드-워셜
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • Effective C++
  • 트리
  • BFS
  • set
  • 알고리즘
  • 디자인 패턴
  • 기술 질문
  • unreal
  • 정렬
  • 개발
  • 최단 경로
  • 우선순위 큐
  • dfs
  • BOJ
  • C++
  • programmers
  • 그래프
  • stl
  • DP
  • Unreal Blueprint

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#1058_친구, 최단 경로, 길 찾기, 플로이드-워셜
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.