글 읽기 - 파이썬) 어디가 잘못됐는지 모르겠습니다.

jintak0401 4년 전 0

코드가 어떻게 동작하는지 설명드리자면

bfs 함수는 인자로 받는 down 이상, up 이하의 수만 있는 길을 따라 도착지까지 가는 함수입니다.

solve 함수는 입력으로 받은 필드인 arr 과 필드의 숫자 종류를 정렬해 놓은 num 리스트를 인자로 받습니다. 그리고 이분탐색을 하는데

먼저 출발지부터 도착지까지 가는 루트 중 최대값이 최소가 되는 길을 찾습니다. 그 길의 최대값은 num[right] 가 됩니다. ( right 가 해당 루트의 최대값이 존재하는 num 리스트내 인덱스 입니다.)

그리고 출발지부터 도착지까지 가는 루트 중, 최대값이 num[right] 이면서 최솟값이 최댓값이 되는 루트를 찾습니다. 그 길의 최솟값은 num[left]가 됩니다.

어디가 잘못되었을까요? 반례만 알려주셔도 감사합니다.

from sys import stdin
from collections import deque

def bfs(arr, down, up):

    if not down <= arr[0][0] <= up:
        return False
    
    d = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    q = deque([(0, 0)])
    visited = set([(0, 0)])
    target = (len(arr) - 1, len(arr[0]) - 1)

    while q:
        pt = q.pop()
        if pt == target:
            return True
        for dx, dy in d:
            x, y = pt[0] + dx, pt[1] + dy

            if 0 <= x < len(arr) and 0 <= y < len(arr[0]):

                if down <= arr[x][y] <= up and (x, y) not in visited:
                    q.append((x, y))
                    visited.add((x, y))
    return False


def solve(arr, num):
    
    left, right = 0, len(num) - 1

    up, down = len(num) - 1, 0
    while up >= down:
        mid = (up + down) // 2
        if bfs(arr, num[0], num[mid]):
            up = mid - 1
            right = mid
        else:
            down = mid + 1

    up, down = right, 0
    while up >= down:
        mid = (up + down) // 2
        if bfs(arr, num[mid], num[right]):
            down = mid + 1
            left = mid
        else:
            up = mid - 1

    return left, right



input = stdin.readline

size = int(input())
arr = []
num = set()
for _ in range(size):
    user_input = list(map(int, input().split()))
    arr.append(user_input)
    num |= set(user_input)

num = list(num)
left, right = solve(arr, num)
print(num[right] - num[left])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬) 어디가 잘못됐는지 모르겠습니다.

jintak0401 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말