Study/BOJ

[BOJ] 1219. 오민식의 고민

MuviSsum 2020. 11. 8. 21:18

 

www.acmicpc.net/problem/1219

 

1219번: 오민식의 고민

첫째 줄에 도착 도시에 도착할 때, 가지고 있는 돈의 액수의 최댓값을 출력한다. 만약 오민식이 도착 도시에 도착하는 것이 불가능할 때는 "gg"를 출력한다. 그리고, 오민식이 도착 도시에 도착

www.acmicpc.net

문제: 민식이가 S 도시부터 E 도시까지 가서 벌 수 있는 돈의 최댓값을 구하여라.

 

민식이의 고민보다 더 고통스러운 고민이었던 것 같습니다..ㅠ

문제를 풀면서 16~17퍼에서 자꾸 WA가 떠서 정말 힘들었던 문제에요.

 

최종적으로 찾아낸 반례는

4 0 3 4
0 1 0
0 3 5
1 2 0
2 1 0
0 5 5 10

답: 5

입니다.

타임머신이나 웜홀에서 썻던 코드를 들고와서 재사용했던게 문제가 되네요.

 

밑을 보시면 벨만포드(BF)쪽 코드는 비슷합니다.

다만 안에 check가 추가되어 있다는 점입니다.

check는 dfs를 사용했습니다.

q라고 되어있어서 bfs로 착각할 수도 있지만 그건 페이크^^

 

어쨋든 사이클을 돈다면 그 사이클에서 E 도시로 갈 수 있어야 합니다.

이게 바로 핵심이죠!

위에 있는 반례를 손으로 그리시다 보면 바로 "아!!" 하실 겁니다 ㅎㅎ

다들 화이팅~~!

 

코드:

def check(E):
    visit = [0] * N
    q = [E]
    while q:
        a = q.pop()
        if a == End:
            return True
        visit[a] = 1
        for b, c in network[a]:
            if visit[b] == 0:
                q.append(b)
    return False


def BF():
    for i in range(N+1):
        if sections[End] == -float('inf') and i == N:
            print('gg')
            return
        for j in range(N):
            if sections[j] == -float('inf'):
                continue
            for E, T in network[j]:
                if sections[j] + T > sections[E]:
                    sections[E] = sections[j] + T
                    if i == N:
                        if check(E):
                            print('Gee')
                            return False
    return True


N, Start, End, M = map(int, input().split())
sections = [-float('inf')] * N
network = [[] for i in range(N)]
for i in range(M):
    S, E, T = map(int, input().split())
    network[S].append([E, T])
salary = list(map(int, input().split()))
sections[Start] = salary[Start]
for i in range(len(salary)):
    for j in range(len(network[i])):
        for k in range(len(salary)):
            if network[i][j][0] == k:
                network[i][j][1] = salary[k] - network[i][j][1]

if BF():
    print(sections[End])
반응형

'Study > BOJ' 카테고리의 다른 글

[BOJ] 17135. 캐슬디펜스  (0) 2021.02.03
[BOJ] 17471. 게리맨더링  (0) 2021.02.02
[BOJ] 9251. LCS  (0) 2020.11.06
[BOJ] 12865. 평범한 배낭  (1) 2020.11.06
[BOJ] 1365. 꼬인 전깃줄  (0) 2020.11.04