글 읽기 - BFS로 모든 경로 탐색 하는법

se5674 1년 전 0

find - union 으로 현재 처리중인 노드가 도착지점까지 갈 수 있는지 확인하고

갈 수 있다면 경로를 탐색하여(DFS) 도착지점 까지 운반가능한 중량의 최대값을 구하는 코드인데

시간초과가 떠서 그런데 혹시 BFS로 하면 시간 초과가 안뜰까요??

구글링 해봐도 BFS로 모든 경로를 탐색하는 방법은 안나오네요 ...

import sys
sys.setrecursionlimit(10**5)
input=sys.stdin.readline
INF=int(1e9)
n,m=map(int,input().split())
graph=[[] for _ in range(n+1)]
weight=[0]*(n+1)
parent=[k for k in range(0,n+1)]

def find_parent(parent,x):
    if parent[x]!=x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]

def union(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b
        
for _ in range(m):
    a,b,cost=map(int,input().split())
    graph[a].append((b,cost))
    graph[b].append((a,cost))
    union(parent,a,b)
start,end=map(int,input().split())
for k in range(1,n+1):
    find_parent(parent,k)  
    
def dfs(v): 
    if v==end:
        return
    else:
        if parent[v]==parent[end]:   ## end까지 도달할 수 있는경우만 탐색
            for k in graph[v]:
                
                if visited[k[0]]==0:
                    visited[k[0]]=1 
                    if weight[v]>k[1]:    ## 중량의 최댓값만 저장
                        if k[1]>weight[k[0]]:
                            weight[k[0]]=k[1]
                    else:
                        if weight[v]>weight[k[0]]:
                            weight[k[0]]=weight[v]
                        
                    dfs(k[0])
                    visited[k[0]]=0  ## 방문한거 삭제
                    
                
weight[start]=INF          
visited=[0]*(n+1)
dfs(start)
print(weight[end])
                
            
            
            

herdson 1년 전 0

문제에 이미 도착지까지 갈 수 있다고 설명하고 있습니다.

시작점, 도착점 연결 확인을 목적으로 유니온 파인드는 전혀 사용할 이유가 없습니다.

그리고 모든 경로를 탐색할 필요 없이 어떤 조건을 만족하는 경로 하나만 찾아도 됩니다.

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

문제

문제

출처

ICPC

BFS로 모든 경로 탐색 하는법

se5674 1년 전 0

herdson 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말