백준 11403 경로 찾기

22.00m

나의 답 (이왜됨..?)

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
tree = [[] for _ in range(n)]

for i in range(n):
    row = list(map(int, input().rstrip().split()))
    for j in range(n):
        if row[j] == 1:
            tree[i].append(j)

def bfs(i, j):
    visited = [False] * n
    visited[i] = True
    q = deque()
    q.append(i)
    while q:
        prev = q.popleft()
        for r in tree[prev]:
            if r == j:
                return True
            if not visited[r]:
                q.append(r)
                visited[r] = True
    return False

res = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if bfs(i, j): res[i][j] = 1

for row in res:
    print(*row, sep=' ')

트리인~~척하는 bfs로 풀었다.
백퍼 시간초과 나겠지..? 하 하면서 제출했는데 원트 성공해서 묘했다.
그래서 찐 답을 좀 찾아봤다.

BFS

내가 푼 답과 일치

코드를 조금 개선해보려고했는데, 찾아보니 그냥 1차원으로 관리하던걸 2차원 자체로 관리하는 정도 였다!

플로이드 워셜

우선 공부를 좀..!

이 문제에 대한 답은 아니지만, 기본적으로 플로이드 워셜은 모든 정점에서 모든 경로의, i부터 j까지 거리의 최소값을 구하는 알고리즘이었다.
이를 파이썬으로 구현하면 아래와 같다.

import sys
input = sys.stdin.readline

n = int(input().rstrip())
tree = [list(map(int, input().rstrip().split())) for _ in range(n)]

for k in range(n): #거치는 점
    for i in range(n): #시작 점
        for j in range(n): #끝 점
            if tree[i][j] > tree[i][k] + tree[k][i]:
                tree[i][j] = tree[i][k] + tree[k][i]

사실 이 문제에서는 최소값이든 뭐든 상관 없으니, 그냥 갈 수 있는지 없는지만 1과 0으로 구분하면 된다.
때문에 더 쉽다!

import sys
input = sys.stdin.readline

n = int(input().rstrip())
tree = [list(map(int, input().rstrip().split())) for _ in range(n)]

for k in range(n): #거치는 점
    for i in range(n): #시작 점
        for j in range(n): #끝 점
            if tree[i][k] and tree[k][j]:
                tree[i][j] = 1

for row in tree:
    print(*row, sep=' ')

코드가 말도안되게 짧아졌다...

성능도 더 좋은 것 같다아
플로이드 워셜 재밌네!