글 읽기 - 논리적 오류가 어디있는지 알려주세요

jintak0401 4년 전 0

코드가 동작하는 방법은 일단 지역별로 연결된 지역과 거리를 딕셔너리로 관리합니다. 입력예제의 경우

{0: {3: 5, 1: 3}, 3: {0: 5}, 4: {1: 4, 2: 1}, 1: {4: 4, 2: 3, 0: 3}, 2: {1: 3, 4: 1}} 와 같습니다.

그리고 dfs 를 통해 탐색을 하는데 어디가 잘못된 것인지 모르겠습니다.

<변수>

zone : 지역개수

item : 지역별 아이템 개수

path : 위의 딕셔너리

visited : 방문한 지역

dist : 남은 탐색거리

from sys import stdin
from collections import defaultdict

def dfs(item, path, n, dist, visited):
   
    ret_val = item[n]
    for i in path[n]:
        if dist >= path[n][i] and i not in visited:
            visited.add(i)
            ret_val += dfs(item, path, i, dist - path[n][i], visited)

    return ret_val

input = stdin.readline
zone, dist, path_num = map(int, input().split())
item = list(map(int, input().split()))
path = defaultdict(dict)
for _ in range(path_num):
    a, b, c = map(int, input().split())
    path[a - 1][b - 1] = c
    path[b - 1][a - 1] = c

ans = 0

for i in range(zone):

    visited = {i}
    ans = max(ans, dfs(item, path, i, dist, visited))

print(ans)

jintak0401 4년 전 4

오류는 dfs 에 있었습니다. visited 에 있었으면(전에 방문했었으면) 다시 가지 않게끔 코드를 짰는데, 만약 다른 루트로 왔을 때 dist 가 더 길 수 있었습니다.

그래서 방문했던 지역도 다시 방문하되, 이미 전에 방문했었으면 아이템 개수를 더해주지 않고, 만약 방문하지 않았으면 아이템 개수를 더해주는 방법으로 고쳤더니 맞더라구요

bigyou98 1년 전 0

위에 분 최고!

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

문제

문제

출처

ICPC

논리적 오류가 어디있는지 알려주세요

jintak0401 4년 전 0

jintak0401 4년 전 4

bigyou98 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말