728x90
반응형
※ 문제링크
※ 관련개념
해당 문제는 플로이드 와샬 알고리즘을 활용하여 풀 수 있는 문제였다. 가중치자체를 갱신하고 기록하지 않아도 되는 문제로 단순하게간선여부만 확인하면 되었기에 코드를 작성하는데 큰 어려움없이 풀 수 있었다. 자세한 문제풀이 방법과 코드는 아래와 같다.
1. 입력값을 바탕으로 2차원배열을 만든다.
2. 3중 반복문을 통해 각각의 정점을 경유하여 특정 정점으로 갈 수 있는지를 확인하고 갱신한다.
3. 반복문이 종료된 이후 출력형식에 맞게 결과값을 출력해준다.
+ 시간 및 메모리 절감을 위해 sys를 사용하였습니다.
import sys
# input = sys.stdin.readline
N = int(input())
matrix = []
for _ in range(N):
sample = list(map(int, input().split()))
matrix.append(sample)
for cp in range(N):
for i in range(N):
for k in range(N):
if matrix[i][k] == 0 and matrix[i][cp] + matrix[cp][k] == 2:
matrix[i][k] = 1
for i in range(N):
print(*matrix[i])
P.S 더 나은 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.
728x90
반응형
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ] 16236번 아기 상어 / 사용언어 : 파이썬(python) (0) | 2022.01.23 |
---|---|
[BOJ] 2583번 영역 구하기 / 사용언어 : 파이썬(python) (0) | 2022.01.23 |
[BOJ] 2468번 안전 영역 / 사용언어 : 파이썬(python) (0) | 2022.01.22 |
[BOJ] 17142번 연구소3 / 사용언어 : 파이썬(python) (0) | 2022.01.22 |
[BOJ] 11404번 플로이드 / 사용언어 : 파이썬(python) (0) | 2022.01.21 |
댓글