글 읽기 - [Python] BFS접근 왜틀렸을까요

halo726 2년 전 0

bfs방식으로 접근했습니다..

틀린 반례나 이유를 알 수 가없습니다..

작은 가중치로 정렬뒤 점을 방문한 여부를 통해 찾아가는 방식입니다..

알려주세요 고수님들 !!

7
12
1 2 3
1 3 2
3 2 1
2 5 2
3 4 4
7 3 6
5 1 5
1 6 2
6 4 1
6 5 3
4 5 3
6 7 4

이 반례를 넣고 문제점을 알아냈습니다

화이팅~

# 1922
n = int(input())
m = int(input())
arr = []
for i in range(m):
    arr.append(list(map(int, input().split())))
arr.sort(key=lambda x: x[-1])

def bfs():
    a,b,c = arr[0]
    queue = []
    queue.append([a,b])
    visit = [0 for i in range(n+1)]
    visit[a] = 1
    visit[b] = 1
    total = c
    while queue:
        if sum(visit) == n:
            break
        nx,ny= queue.pop(0)
        for i in range(m):
            a,b,c = arr[i]
            if (visit[a] == 0 or visit[b] == 0) and ((a == nx or a == ny) or (b == nx or b == ny)):
                total += c
                queue.append([arr[i][0], arr[i][1]])
                visit[a] = 1
                visit[b] = 1
                break
    print(total)
bfs()

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

문제

문제

출처

ICPC

[Python] BFS접근 왜틀렸을까요

halo726 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말