글 읽기 - 혹시 제 코드에서 반례를 좀 찾아주실수 있으실까요.

okqwaszx123 2년 전 0

아래처럼 작성했을때, 혹시 어떤 반례가 있을지 잘 파악이 안되네요

제가 작성한 코드가 어떤부분에서 틀렸는지 반례 찾아주시면 감사하겠습니다.

class Queue:
    
    def __init__(self, capacity):
        self.max = capacity
        self.que = [0] * self.max
        self.data = 0
        self.front = 0
        self.rear = 0

    def enqueue(self, x):
        if self.data >= self.max:
            raise IndexError
        self.que[self.rear] = x
        self.data += 1
        self.rear += 1
        if self.rear == self.max:
            self.rear = 0
        return x

    def dequeue(self):
        if self.data <= 0:
            raise IndexError
        now = self.que[self.front]
        self.data -= 1
        self.front += 1
        if self.front == self.max:
            self.front = 0
        return now
         
    def isEmpty(self):
        return self.data <= 0


# 현재 노드를 dequeue 한뒤, 여기서 방문 가능한 노드들 체크, 그 중
# 1. 방문 안했고, 2. 수색범위 안에 있을때만 진행
def bfs(start, n, m, graph, item):
    que = Queue(n*n)
    visited = [False] * (n+1)
    # 아이템은 0 ~ n-1 까지 저장되있다 주의!
    res = 0
    que.enqueue((0, start))
    visited[start] = True
    while not que.isEmpty():
        now = que.dequeue()
        now_cost = now[0]
        now_node = now[1]
        res += item[now_node-1]
        for cost, next_node in graph[now_node]: 
            # 이미 방문한 경우
            if visited[next_node]:
                continue
            # 수색범위 벗어난 경우
            if now_cost + cost > m:
                continue  
            visited[next_node] = True
            next_cost = now_cost + cost
            que.enqueue((next_cost, next_node)) 
    return res
        

N, M, R = map(int, input().split())
I = list(map(int, input().split()))
G = [[] for _ in range(0, N+1)]

# 양방향 그래프
for i in range(0, R):
    a, b, c = map(int, input().split())
    G[a].append((c, b))
    G[b].append((c, a))

max_count = 0
for i in range(1, N+1):
    now = bfs(i, N, M, G, I)
    if max_count <= now:
        max_count = now
print(max_count)

whiteleo100 1년 전 2

이미 방문했더라도 거리가 더 짧게 방문한다면 이전에는 가지 못 한 노드를 갈 수 있습니다.

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

문제

문제

출처

ICPC

혹시 제 코드에서 반례를 좀 찾아주실수 있으실까요.

okqwaszx123 2년 전 0

whiteleo100 1년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말