<세일즈맨의 고민>
난이도 : 플래티넘 5
-
백준 문제
1219 -
코드 알고리즘
- 1번째 시도
2-1. 1번째 시도 슈도코드
#벨만포드 먼저 실행
for 에지 개수만큼 반복:
에지 리스트에 에지 정보저장
이때 -가중치로 저장
거리리스트 0 초기화
건물 가격
#근데 출발노드에서 시작하도록 해야됨
for 노드개수 -1 :
for 에지개수 반복:
현재 에지 데이터 가져오기:
if 출발노드!=inf : #출발노드는 inf이면 제외해야됨
if 도착노드 == inf: #이때는 처음이므로 넘어가주기
D[도착노드] = D[출발 노드] + 에지 가중치 #무조건 바꿔주기
else:
if D[도착노드] < D[출발 노드] + 에지 가중치: #INF가 아닌 경우에는 더 큰 값으로 바꿔주기
D[도착노드] = D[출발 노드] + 에지 가중치
#업데이트 검사
-> 이때 반례들 제외
for 에지 개수 반복:
현재 에지 데이터 가져오기
-> distance 초기화를 [0, max, max... ]에서 [0, min, min ... ]으로 변경
-> 음수 사이클에서 양수 사이클을 찾아내야 됨
-> 양수 사이클 예외 찾기
-> BFS로 양수 사이클 예외 찾기
- 2번째 시도
2-2. 2번째 시도 슈도코드
#새로운 슈도코드
A = 인접리스트 #bfs에 사용될 리스트
for 에지 개수만큼 반복:
에지 리스트에 에지 정보저장
인접리스트에도 반영하기 A[start].append(end)
이때 -가중치로 저장
거리리스트 -sys.maxsize(=min) 대입
출발노드는 0 초기화
cityMoney 저장
if 출발노드 == 도착노드:
출발노드의 cityMoney 출력한 후 종료
else:
출발노드는 0으로 초기화
벨만포드 함수 실행
존재 유무 = 양수사이클_확인 함수 실행
if False:
최종 체크 함수 실행
else (True):
if BFS(start, end) #업데이트 됐으므로 반드시 start 노드와 양수사이클 연결되있음. end와 연결되있는지만 확인하면 됨!!
#True 인경우이므로 Gee 출력
print(Gee)
else:
최종 체크 함수 실행
#벨만포드 함수
벨만포드( ):
#출발노드가 0이던 아니던 간에 노드개수 * 에지 개수만큼 다 돌아야 정보 알 수 있음
#출발노드를 0이 아닌 수로 설정만 해주면 됨(즉, 반복 횟수는 변하지 않는다)
for 노드개수 -1 :
for 에지개수 반복:
현재 에지 데이터 가져오기:
if 출발노드!=min and D[도착노드] < D[출발 노드] + 에지 가중치 +도착도시 가격: #min가 아닌 경우에는 더 큰 값으로 바꿔주기
D[도착노드] = D[출발 노드] + 에지 가중치 + 도착도시가격 #업데이트
#양수사이클 함수 실행
양수사이클( ):
for 에지개수 반복:
현재 에지 데이터 가져오기
if 출발노드 != min and D[도착노드] < D[출발 노드] + 에지 가중치:
업데이트 했으므로 return True # 양수사이클 존재 의미
#BFS
BFS(start, end):
queue 선언
queue에 start append
while queue:
현재노드 queue에 popleft
if 현재노드 == end:
return True #end를 방문했다는 뜻이므로 이건 Gee인 경우
else :
for i in A[now_node]:
if not visited:
방문 체크
큐에 삽입
#최종 체크 함수
최종체크():
if D[end] == min:
print(gg)
else:
print(D[end])
2-3. 반례
- 반례 테케 모음
1.
4 1 3 4
0 1 0
0 1 100000
1 2 3
2 3 4
2 2 2 2
ans = -1
------------------
2.
4 0 1 4
0 1 0
3 1 10
2 3 3
3 2 3
0 10 10 10
ans = 10
------------------
3.
1 0 0 2
0 0 0
0 0 7
6
ans = Gee- 코드
#1219
#https://www.acmicpc.net/problem/1219
import sys
input = sys.stdin.readline
from collections import deque
N, start, end, M = map(int, input().split())
edge_list = [[] for i in range(M)] #에지 개수만큼 리스트 만들기 (0에서 시작함을 주의)
min = -sys.maxsize
D = [min]*(N) #도시가 0부터 시작하므로 N+1 해줄 필요X
D[start] = 0
queue = deque()
visited = [0]*(N)
for i in range(M):
s, e, w = map(int, input().split())
edge_list[i]=(s,e,-w)
#cityMoney 입력
cityMoney = list(map(int, input().split()))
D[start] += cityMoney[start] #시작 도시 가격도 포함되도록 장치해두기
#함수 정의
def bfm(): #bellman-ford-moore
for j in range(N-1): #왜 N-1번 만큼 또 반복하는 거지..? 벨만포드 핵심을 아직 이해못함 --> 다시 정리
for i in range(M):
node_now = edge_list[i] #(s,e,w)
if D[node_now[0]] != min and D[node_now[1]] < D[node_now[0]] + node_now[2] +cityMoney[node_now[1]] :
#D[도착] < D[출발] + 가중치 + cityMoney[도착]
D[node_now[1]] = D[node_now[0]] + node_now[2] +cityMoney[node_now[1]]
ans = False
def cycle_check():
global ans
for i in range(M):
node_now = edge_list[i] # (s,e,w)
if D[node_now[0]] != min and D[node_now[1]] < D[node_now[0]] + node_now[2] +cityMoney[node_now[1]]:
queue.append(node_now[0]) #출발노드가 cycle_node
visited[node_now[0]] = 1
ans = True #양수사이클 존재
def BFS():
#cycle_node가 start_node임을 주의 ★★★
while queue:
now = queue.popleft()
if now == end:
return True
else:
#start 제외된(이미 체크됐으므로) 에지에 있는 출발 노드들로부터 시작해서 end 노드 도착하는지 확인하기
#사이클이랑 end 연결됐다면 임의의 사이클 노드 1개와 end 무조건 연결
for i in range(M):
temp = edge_list[i] #(s,e,w)
if temp[0] == now and visited[temp[1]]==0: #edge_list 중 cycle_node 찾기, 그리고 next에 해당되는 temp[1]이 방문하지 않은 경우
visited[temp[1]] = 1
queue.append(temp[1])
return False
def result_print():
if D[end] == min:
print("gg")
else:
print(D[end])
bfm() #벨만포드 함수 실행
cycle_check()
if not ans: #False
result_print()
else: #True
if BFS(): #True ~ 양수사이클과 연결
print("Gee")
else:
result_print()
# N=1인 경우 https://www.acmicpc.net/board/view/110065
# start == end 반례 경우
- 코드 후기
이거땜에 밤샜다...
나중에 쓸게요...
for well-being we need nectar and ambrosia