[백준-파이썬] 10282: 해킹

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

컴퓨터 간 의존성이 주어진다. a가 b를 의존하면, b가 감염되면 a도 감염된다는 뜻이다. b가 감염된 후 a가 감염될 때까지의 시간도 알려준다. 해킹 당한 컴퓨터를 알려주면, 그 컴퓨터를 포함해서 총 몇 대가 감염되는지, 얼마나 시간이 걸리는지 구해야 한다.

처음에는 서로 연결되었는지 봐야 하니까 유니온 파인드가 잠깐 떠올랐다가, 얼마나 시간 걸리는지도 체크해야 하니까 접었다. 고민하다 보니 플로이드 워샬이 떠올랐다. 한 컴퓨터에서 다른 컴퓨터로 연결되는지, 해킹될 때까지 얼마나 시간이 걸리는지를 구할 수 있으니까 !! (플로이드 워샬로 해도 답은 나오잖아요 ? 메모리, 시간이 문제지..)

풀이 생각난 게 신나서 풀었다.. 예제는 풀리는데, 제출했더니 바로 메모리 초과..
아니 ㅠ 좀만 더 생각해봤으면, 한 점에서 출발하는 경우만 필요하다는 걸 알 수 있었을텐데...
생각을 하자..!!!

한 점(해킹 당한 컴퓨터)에서 출발해서, 다른 점들로 가는 최소 거리(얼마나 시간 걸리는지 여러 방법이 있을 경우에 최소의 시간을 알아야 함)를 구해야 하므로 다익스트라로 풀었다.
그랬더니 맞았다!!

메모리 초과 나는 플로이드 워샬로 푼 코드🐸

import sys

input = sys.stdin.readline

if __name__ == '__main__':
    INF = 10000 * 1000 + 1
    T = int(input())

    for _ in range(T):
        n, d, c = map(int, input().split())
        c -= 1  # 인덱스 편하게 쓰려고
        board = list([INF] * n for _ in range(n))
        for _ in range(d):
            a, b, s = map(int, input().split())
            a -= 1
            b -= 1
            board[b][a] = s

        # 플로이드 와샬
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if i == j:
                        board[i][j] = 0
                    else:
                        board[i][j] = min(board[i][j], board[i][k] + board[k][j])

        # 정답 출력
        cnt = 1
        time = 0
        for i in range(n):
            if i == c:
                continue

            if board[c][i] != INF and board[c][i] != 0:
                cnt += 1
                time = max(time, board[c][i])
        print(f'{cnt} {time}')

다익스트라로 맞은 코드!! 🌸

import sys, heapq

input = sys.stdin.readline

if __name__ == '__main__':
    INF = 10000 * 1000 + 1
    T = int(input())

    for _ in range(T):
        n, d, c = map(int, input().split())
        c -= 1  # 인덱스 편하게 쓰려고

        c_connect = [INF]*n
        board = list([] for _ in range(n))
        for _ in range(d):
            a, b, s = map(int, input().split())
            a -= 1
            b -= 1
            tmp = tuple((s, a))
            board[b].append(tmp)

        # 다익스트라
        visited= [False] * n
        q = []
        heapq.heappush(q, (0, c))
        while q:
            time, computer = heapq.heappop(q) # 그 상황에 젤 가까운 컴퓨터
            if visited[computer]: # 이미 방문했으면 넘어가기
                 continue
            visited[computer] = True

            c_connect[computer] = time
            # 거기와 연결된 컴퓨터들 보기
            for i in range(len(board[computer])):
                time2, computer2 = board[computer][i]
                c_connect[computer2] = min(c_connect[computer2], c_connect[computer] + time2)
                heapq.heappush(q, (c_connect[computer2], computer2))

        # 정답 출력
        cnt = 0
        time = 0
        for i in range(n):
            if c_connect[i] != INF:
                cnt += 1
                time = max(time, c_connect[i])
        print(f'{cnt} {time}')

좀 더 빠르게 😎

정답 출력 아래 for 문을 리스트 컴프리핸션으로 수정하니 시간이 좀 더 빨라졌다!!

  cnt = sum([1 for n in c_connect if n != INF])
  time = max([n for n in c_connect if n != INF])