프로그래머스 - 2019 카카오 개발자 겨울 인턴십 - 튜플

08 May 2020

문제

입력

---

나의 처음 코드

중량제한 문제!!! 이분탐색이랑 bfs로 풀 수 있는 문제이다. 자료구조를 어떻게 짜느냐와 어떻게 탐색을 하냐에 따라서 시간초과가 날 수도, 메모리 초과가 날 수도 있다. 나는 간선을 튜플로 저장하였고, bfs에서 pop으로 인한 시간을 줄이면서 문제를 풀었다. 생각보다 까다로운 문제이다… 코드는 다음과 같다.

N, M = list(map(int, input().split()))
map_list = [[] for _ in range(N)]

min_num, max_num = 1000000001, -1
#섬끼리 중량받기
for _ in range(M):
    a,b,c = list(map(int, input().split()))
    map_list[a-1].append((b-1, c))
    map_list[b-1].append((a-1, c))

# print(map_list) 

#공장 2개 입력받기
start, end = list(map(int, input().split()))
start, end = start - 1, end - 1

def bfs(start, end, mid):
    global N
    visited_list = []
    queue_list = [start]
    visited_list.append(start)
    while True:
        tmp_list = []
        for item in queue_list:
            for info in map_list[item]:
                if info[0] not in visited_list and info[1] >= mid:
                    if info[0] == end:
                        return True
                    tmp_list.append(info[0])
                    visited_list.append(info[0])
        queue_list = tmp_list
        if len(queue_list) == 0:
            return False


left, right = 0, 1000000000

while left <= right:
    mid = (left+right)//2
    result = bfs(start, end, mid)
    if result == True:
        left = mid + 1
    else:
        right = mid - 1

print(right)

이분탐색 문제가 요즘 자주나온다,,, 기준을 어떻게 잡냐가 아직도 어렵다,,,