[백준/파이썬] 11403번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 11403번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.
입력 요약
첫째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄부터 N개 줄에는 그래프의 인접 행렬이 주어진다. i번째 줄의 j번째 숫자가 1인 경우에는 i에서 j로 가는 간선이 존재한다는 뜻이고, 0인 경우는 없다는 뜻이다. i번째 줄의 i번째 숫자는 항상 0이다.
출력 요약
총 N개의 줄에 걸쳐서 문제의 정답을 인접행렬 형식으로 출력한다. 정점 i에서 j로 가는 길이가 양수인 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력해야 한다.
코드
import sys;read=sys.stdin.readline
import collections
n=int(read())
d={}
for i in range(n):
l=list(map(int,read().split()))
for j in range(n):
if l[j]>0:
try:d[i].append(j)
except:d[i]=[j]
r=[[0]*n for _ in range(n)]
for k,v in d.items():
q=collections.deque(v)
while q:
t=q.popleft()
r[k][t]=1
try:
for p in d[t]:
if r[k][p]<1:q.append(p)
except:continue
print('\n'.join(map(lambda x:' '.join(map(str,x)),r)))
설명
핵심은 구현 관점에서 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오.를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기