[11403] 경로 찾기 (플로이드-워셜)

2023. 4. 23. 17:18·Coding Test/Graph
목차
  1. 분석
  2. 풀이
728x90
 

11403번: 경로 찾기

가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

분석

  • 최단거리를 구하는 문제가 아니기 때문에 플로이드-워셜 알고리즘에서 업데이트 부분 수정
  • S와 E가 모든 중간 경로(K) 중 1개라도 연결되어 있다면 S와 E는 연결 노드로 저장

 

풀이

"""
모든 정점 (i,j) i에서 j로 가는 경로가 있는지 없는지
i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력
"""
import sys

# 인접행렬 크기
n = int(input())

# 인접행렬
d = array = [[sys.maxsize for j in range(n)] for i in range(n)]

# 인접 행렬에 시작 도시와 종료 도시가 같은 자리에 0 저장
for i in range(n):
    d[i][i] = 0

for i in range(n):
    d[i] = list(map(int, input().split()))
print(d)

for k in range(n): # 경유지 k
    for s in range(n):
        for e in range(n):
            if d[s][k] ==1 and d[k][e]==1:
                d[s][e]=1

for i in range(n):
    for j in range(n):
        if d[i][j] != sys.maxsize:
            print(d[i][j], end=" ")
        else:
            print(0, end=" ")
    print()

 

 

 

 

728x90
저작자표시 (새창열림)
  1. 분석
  2. 풀이
'Coding Test/Graph' 카테고리의 다른 글
  • [1414] 불우이웃돕기 (MST, 문자열)
  • 최단거리(다익스트라) vs 최소 신장 트리(크루스칼)
  • [1389] 케빈 베이컨의 6단계 법칙 (플로이드-워셜)
  • [17472] 다리 만들기2 (BFS, MST)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    그래프
    Algorithm
    그리디
    재귀
    큐
    월간코드챌린지
    힙
    파이썬
    BFS
    덱
    구간합
    최소신장트리
    최단거리
    알고리즘
    다익스트라
    구현
    DP
    조합
    자료구조
    동적계획법
    이분탐색
    LIS
    백준
    정렬
    스택
    플로이드워셜
    최대공약수
    트리
    DFS
    프로그래머스
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[11403] 경로 찾기 (플로이드-워셜)
상단으로

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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