[BOJ알고리즘, C++]#1613_역사, 플로이드-워셜, 최단 경로, 길 찾기, 그래프 순환 여부

2024. 6. 21. 19:51· 문제 풀이/BOJ 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 플로이드-워셜 알고리즘
  4. 3. 전체-쌍 관계? 플로이드-워셜!
  5. #3. 코드

 

#1. 문제

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

 


 

#2. 풀이

 

1. 플로이드-워셜 알고리즘

 

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

#1. 개념 1. 길 찾기 알고리즘[정의] : 길 찾기 알고리즘은 그래프 자료구조에서 출발점에서 도착점 사이의 경로를 탐색하는 알고리즘입니다. 노드와 노드 간 연결 관계를 나타내는 간선으로 구

webddevys.tistory.com

플로이드-워셜 알고리즘은 음수 가중치를 포함한 그래프에서 '전체-쌍' 최단 경로를 찾는 알고리즘입니다. 특히, 주어진 문제에서 '경유 정점' 혹은 전체-쌍과 그래프 순환 여부에 대해서 언급할 경우, 플로이드-워셜 알고리즘 활용 가능성이 높아집니다. 

 

3. 전체-쌍 관계? 플로이드-워셜!

  1.  그래프 구성 시 두 정점 사이의 선행 관계를 기억해 줍니다.
  2. 플로이드-워셜을 수행하며, '경유 정점'을 통한 선행 관계 업데이트 여부를 확인하고 선행 관계를 업데이트해 줍니다. 

 


 

#3. 코드

/*
    @문제: 주어진 사건의 전후 관계를 통해 문제의 두 사건의 선후 관계를 파악
    @설명
        1. 위상정렬 - 진입차수BFS(x) 왜? DAG(비순환 유향 그래프)에서만 활용 가능한 알고리즘!!!
        2. 플로이드-워셜 - 선행 관계 파악에서, '순환 여부'를 확인하고, 순환 여부 가능성이 존재한다면 플로이드-워셜 활용!!
*/

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

#define MAX 401

int n, k, s;

vector<vector<int>> graph;

void floyd()
{
    for(int k=1; k<=n; ++k)
    {
        for(int u=1; u<=n; ++u)
        {
            for(int v=1; v<=n; ++v)
            {
                // u->v 선행 관계 모름, u->k 와 k->v의 선행 관계가 존재하고, 그 관계가 같다면 업데이트
                if(graph[u][v] == 0 
                && graph[u][k] != 0 && graph[k][v] != 0 
                && graph[u][k] == graph[k][v])
                {
                    graph[u][v] = graph[u][k];
                    graph[v][u] = graph[u][k] * -1;
                }
            }
        }
    }
}

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

    cin >> n >> k;

    graph.resize(n+1, vector<int>(n+1, 0));
    while(k--)
    {
        int u, v;
        cin >> u >> v;

        graph[u][v] = -1;
        graph[v][u] = 1;
    }

    floyd();

    cin >> s;

    while(s--)
    {
        // u가 먼저 일어났으면 -1, v가 먼저 일어났으면 1, 모르면 0
        int u, v;
        cin >> u >> v;
    
        cout << graph[u][v] << '\n';
    }


    return 0;
}

 


 

 

 

 

저작자표시 (새창열림)

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

[BOJ알고리즘, C++]#1219_오민식의 고민, 최단 경로, 최대 경로, 길 찾기, 벨만-포드  (2) 2024.06.25
[BOJ알고리즘, C++]#2512_예산, 이분 탐색, Binary Search  (0) 2024.06.21
[BOJ알고리즘, C++]#13418_학교 탐방하기, 최소 신장 트리, MST, 크루스칼  (0) 2024.06.21
[BOJ알고리즘, C++]#5670_휴대폰 자판, Trie 자료구조, 트리  (0) 2024.06.21
[BOJ알고리즘, C++]#1735_분수 합, 유클리드 호제법, 최대 공약수, 최소 공배수, gcd, lcm  (0) 2024.06.19
  1. #1. 문제
  2. #2. 풀이
  3. 1. 플로이드-워셜 알고리즘
  4. 3. 전체-쌍 관계? 플로이드-워셜!
  5. #3. 코드
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#1219_오민식의 고민, 최단 경로, 최대 경로, 길 찾기, 벨만-포드
  • [BOJ알고리즘, C++]#2512_예산, 이분 탐색, Binary Search
  • [BOJ알고리즘, C++]#13418_학교 탐방하기, 최소 신장 트리, MST, 크루스칼
  • [BOJ알고리즘, C++]#5670_휴대폰 자판, Trie 자료구조, 트리
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

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

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#1613_역사, 플로이드-워셜, 최단 경로, 길 찾기, 그래프 순환 여부
상단으로

티스토리툴바

개인정보

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

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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