글 읽기 - 반례가 뭐가 있을까요? 브루트포스로 풀었습니다

whiteleo100 1년 전 0

dfs로 모든 브루트포스 방식을 이용해봤습니다.

먼저 이전에 방문하지 않았던 노드일 경우 아이템을 더해서 방문하고

이전에 방문하였지만 소모한 거리가 더 짧을 경우 거리때문에 이전에 방문하지 못 한 노드가 있을 수 있으니 아이템을 더하지 않고 방문하는 식으로 코드를 작성해보았는데요 12%에서 틀렸습니다가 나옵니다.

어디가 잘못되었을까요.

import sys, collections
from typing import List
input = sys.stdin.readline
def dfs(m:int,node:int,item:int,distance:List[int]) -> None:
    for road,cost in roads[node]:
        if cost <= m and m - cost < distance[road]:
            if distance[road] == 16: # 이전에 방문 x
                distance[road] = m-cost
                item += dfs(m-cost,road, items[road],distance) # item을 더해준다
            else:
                distance[road] = m-cost
                item += dfs(m-cost,road,0,distance) # 아이템을 더하지 않고 방문
    return item
n,m,r = map(int, input().split())
items = list(map(int,input().split()))
roads = collections.defaultdict(list)
max_item = 0
for _ in range(r):
    a,b,l = map(int,input().split())
    roads[a-1].append([b-1,l])
    roads[b-1].append([a-1,l])
for i in range(n):
    distance = [16 for  _ in range(n)]
    distance[i] = -1
    max_item = max(dfs(m,i,items[i],distance),max_item)

print(max_item)

whiteleo100 1년 전 1

아래 코드 부분이 문제였네요.. 멍청하게 아래처럼 m-cost로 해버리면 남은 거리가 저장되고 road까지 가는 거리가 저장되는게 아니라 남은 거리가 저장되어서 저렇게 하려면 m-cost가 더 큰가를 물어보는게 올바르네요

 for road,cost in roads[node]:
        if cost <= m and m - cost < distance[road]:
            if distance[road] == 16: # 이전에 방문 x
                distance[road] = m-cost

## 수정한 코드

import sys, collections
from typing import List
input = sys.stdin.readline
def dfs(m:int,node:int,item:int,distance:List[int]) -> int:
    for road,cost in roads[node]:
        if cost <= m and distance[road] < m-cost:
            if distance[road] == -1: # 이전에 방문 x
                distance[road] = m-cost
                item += dfs(m-cost,road, items[road],distance) # item을 더해준다
            else:
                distance[road] = m-cost
                item += dfs(m-cost,road,0,distance) # 아이템을 더하지 않고 방문
    return item
n,m,r = map(int, input().split())
items = list(map(int,input().split()))
roads = collections.defaultdict(list)
max_item = 0
for _ in range(r):
    a,b,l = map(int,input().split())
    roads[a-1].append([b-1,l])
    roads[b-1].append([a-1,l])
for i in range(n):
    distance = [-1 for  _ in range(n)]
    distance[i] = 16
    max_item = max(dfs(m,i,items[i],distance),max_item)

print(max_item)

minsu_choi 1년 전 0

오 감사합니다 ㅠㅠ 브루트포스 풀이법 찾는 중이었는데, 거리가 더 짧으면 안 더하고 dfs를 진행하는 방법도 있네요

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

문제

문제

출처

ICPC

반례가 뭐가 있을까요? 브루트포스로 풀었습니다

whiteleo100 1년 전 0

whiteleo100 1년 전 1

minsu_choi 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말