[TIL_Carrotww] 120 - 23/06/13

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 멀티버스2

• 내 생각
  정렬만 잘 하면 된다고 생각했다. 그러니까 죄표압축을 해야하는 것이다.

    for _ in range(M):
        temp = list(map(int, sys.stdin.readline().split()))
        temp = [(idx, val) for idx, val in enumerate(temp)]
        temp.sort(key=lambda x:x[1])
        temp = [idx for idx, val in temp]
        universe.append(','.join(map(str, temp)))

이런식으로 정렬했는데 이렇게 정렬을 하면 같은 숫자 즉 123123이 들어왔을때 작은 수부터 큰 수대로 정렬하면 024135 이렇게 된다. 같은 숫자가 같은 인덱스로 들어가지 못하기 때문에 다시 짜야한다.
아래는 최종 풀이다.

• 풀이

def solve():
    import sys
    from collections import defaultdict
    M, N = map(int, sys.stdin.readline().split())

    uni_dict = defaultdict(int)
    for _ in range(M):
        temp = list(map(int, sys.stdin.readline().split()))
        s_temp = sorted(set(temp))
        temp_dict = dict()
        str_uni = ''
        for i in range(len(s_temp)):
            temp_dict[s_temp[i]] = i
        for te in temp:
            str_uni += str(temp_dict[te])
        uni_dict[str_uni] += 1

    result = 0
    for i in uni_dict.values():
        result += (i * (i - 1)) // 2

    print(result)

if __name__ == "__main__":
    solve()

정렬만 잘 하면 쉽게 풀리는 문제다.

🔍 백준 해킹

bfs로 할지 다익스트라로 할지 고민하다가 다익스트라로 그냥 했다.
기본적인 다익스트라 문제지만 입력이 어떻게 들어오는지 살짝 헷갈려서 문제를 3번정도 읽었던 것 같다.
문제만 이해하고 있으면 쉽게 풀린다.
그리고 결과값을 출력하는게 귀찮은걸 요구하지만 그것만 잘 처리해주면 끝

• 내 풀이

def solve():
    import sys, heapq
    from collections import defaultdict
    n, d, c = map(int, sys.stdin.readline().split())
    dpcy = defaultdict(list)
    visited = [float('inf')] * (n+1)
    for _ in range(d):
        a, b, t = map(int, sys.stdin.readline().split())
        dpcy[b].append([a, t])
    heap = []
    heap.append([0, c])
    visited[c] = 0
    cnt, result = 0, 0

    while heap:
        time, node = heapq.heappop(heap)
        for nnode, ttime in dpcy[node]:
            if visited[nnode] > ttime + time:
                visited[nnode] = ttime + time
                heapq.heappush(heap, [ttime + time, nnode])

    temp = [x for x in visited if x != float('inf')]
    cnt, result = len(temp), max(temp)

    return cnt, result

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline())
    for _ in range(N):
        a, b = solve()
        print(f'{a} {b}')