[백준] 1939번 중량제한 _ Python

2023. 11. 20. 23:15·Algorithms/Binary Search

[초기 접근 방법(x)]

1. 직행 다리가 감당이 가능하면, 가능한 중량을 올린다.

 

2. 직행 다리가 감당이 불가능하면, 경유 다리를 탐색하자

     1) 경유 다리가 감당이 불가능한 경우, 가능한 중량을 내린다.

     2) 경유 다리가 감당이 가능한 경우, 가능한 중량을 올린다.

 

 

 

[생각]

위와 같이 접근을 하게 되면

감당 가능한 무게가 작은, 쓸데없는 다리가 있을 경우에

목적지까지 갈 수 있음에도 판단하지 못한다.

 

- search 함수를 다음과 같이 작성하면 틀린다. 왜??

def search(start, end):
    while start < end:
        mid = (start + end) // 2

        # 다리들이 현재 mid 무게를 감당 가능하면, 더 중량을 올려도 됨
        if bfs(mid):
            start = mid + 1

        # 감당 불가능하면
        else:
            end = mid

    return end

 

 

 

 

[참고해서 작성한 코드]

# 풀이 시간 : 50분 + 30분
# 시간복잡도 : O((N+M)*log(max(weight)))
# 공간복잡도 : O(N)
# 참고 : https://jie0025.tistory.com/212

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

def bfs(mid):
    visited = [False] * (N+1)
    q = deque()
    q.append(endA)

    while len(q) > 0:
        dot = q.popleft()
        visited[dot] = True

        if dot == endB:
            return True

        for b, c in bridge[dot]:
            # 다음 목적지가 아직 방문하지 않은 '섬'일 경우 & 감당가능한 '다리'일 경우
            if not visited[b] and c >= mid:
                visited[b] = True # 큐에 계속 들어와지는 걸 막기 위해
                q.append(b)

    return False


def search(start, end):
    while start <= end:
        mid = (start + end) // 2

        # 다리들이 현재 mid 무게를 감당 가능하면, 더 중량을 올려도 됨
        if bfs(mid):
            start = mid + 1

        # 감당 불가능하면
        else:
            end = mid - 1

    return end

# N : N개의 섬,
N, M = map(int, input().split())

bridge = [[] for _ in range(N+1)]
weight = [] # 각 다리가 버틸 수 있는 무게 집합

for _ in range(M):
    a, b, c = map(int, input().split())

    bridge[a].append((b, c))
    bridge[b].append((a, c))
    weight.append(c)

endA, endB = map(int, input().split())

# 무게 최소, 최대
print(search(1, max(weight)))
저작자표시 (새창열림)

'Algorithm > Binary Search' 카테고리의 다른 글

[백준] 1300번 K번째 수 _ Python  (0) 2023.11.17
[백준] 11663번 선분 위의 점 _ Python  (1) 2023.11.13
[백준] 13397번 구간 나누기 2 _ Python  (0) 2023.11.12
[백준] 19637번 IF문 좀 대신 써줘 _ Python  (0) 2023.11.11
[백준] 2417번 정수 제곱근 _ Python  (1) 2023.11.11
'Algorithms/Binary Search' 카테고리의 다른 글
  • [백준] 1300번 K번째 수 _ Python
  • [백준] 11663번 선분 위의 점 _ Python
  • [백준] 13397번 구간 나누기 2 _ Python
  • [백준] 19637번 IF문 좀 대신 써줘 _ Python
wch_t
wch_t
  • wch_t
    끄적끄적(TIL)
    wch_t
  • 글쓰기 관리
  • 전체
    오늘
    어제
    • 분류 전체보기 (171)
      • Architecture (0)
      • Algorithm (67)
        • Math (5)
        • Simulation (1)
        • Data Structure (4)
        • DP (7)
        • Brute Fource (10)
        • Binary Search (6)
        • Greedy (2)
        • Graph (11)
        • Mst (1)
        • Shortest path (10)
        • Two Pointer (1)
        • Tsp (3)
        • Union Find (2)
        • Mitm (1)
      • CS (2)
        • 데이터베이스 (5)
        • 네트워크 (5)
      • DB (6)
      • DevOps (17)
        • AWS (9)
        • Docker (1)
        • CI-CD (5)
      • Error (1)
      • Project (0)
        • kotrip (0)
      • Spring (59)
        • 끄적끄적 (5)
        • 기본 (9)
        • MVC 1 (7)
        • MVC 2 (11)
        • ORM (8)
        • JPA 1 (7)
        • JPA 2 (5)
        • Spring Data Jpa (7)
      • Test (2)
      • TIL (6)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    apache poi
    docker
    spring-cloud-starter-bootstrap
    Jenkins
    aws secrets manager
    response_mode
    백준 17299 파이썬
    spring-cloud-starter-aws-secrets-manager-config
    form_post
    TempTable
    view algorithm
    애플
    scope
    백준 3015 파이썬
    백준 17289 파이썬
    Merge
    docker: not found
    Sxssf
  • 최근 댓글

  • hELLO· Designed By정상우.v4.10.3
wch_t
[백준] 1939번 중량제한 _ Python
상단으로

티스토리툴바