파이썬 알고리즘 306번 | [백준 14983번] 서강 그라운드 - 다익스트라, 플로이드 워셜

306. 서강 그라운드

1) 어떤 전략(알고리즘)으로 해결?

다익스트라, 플로이드 워셜

2) 코딩 설명

<내 풀이>

from collections import defaultdict, deque
import heapq
import sys

#지역의 개수 n (1 ≤ n ≤ 100) / 예은이의 수색범위 m (1 ≤ m ≤ 15) / 길의 개수 r 
n,m,r = map(int,sys.stdin.readline().rstrip().split())
# 지역 간 간선 담아주는 사전
relation = defaultdict(list)
# 지역별 아이템 갯수 : 1번 지역~n번 지역 맞춰줄라고 맨 앞에 0 넣음
item_per_area = [0]+list(map(int,sys.stdin.readline().rstrip().split())) 

for i in range(r) : 
    a,b,l = map(int,sys.stdin.readline().rstrip().split())
    # 가장 적은 길이의 연결 노드 순으로
    heapq.heappush(relation[a],((l,b)))
    heapq.heappush(relation[b],((l,a)))

for rk in relation : 
    relation[rk].sort()

# 예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
# 각 지역마다 떨어뜨린 후 얻을 수 있는 최대 아이템 개수
def dik(start_area) : 
    min_road = [ int(1e9) for _ in range(n+1)]
    min_road[start_area] = 0
    q = deque()
    q.append((start_area, 0)) # 현재 노드 /  길의 길이
    item_cnt = 0

    while q :  
        now_area, now_length= q.popleft()
        if now_length > min_road[now_area] : # 볼 필요 없는 경우
            continue
        
        for j in range(len(relation[now_area])) : 
            next_length, next_area = relation[now_area][j]
            if next_length+now_length < min_road[next_area]: 
                min_road[next_area] = next_length+now_length
                q.append((next_area, next_length+now_length))

    # 위와 같이 돌면 각 지역까지의 최소거리 존재합니다. 
    # 최소거리들 중 범위를 넘지 않는 애들 아이템만 collect
    for area in range(1,n+1) : 
        if min_road[area]<=m : 
            item_cnt+=item_per_area[area]
    
    return item_cnt

##############################################################################

answer = 0
for area in range(1,n+1) :
    answer = max(answer, dik(area))
print(answer)

• 플로이드 워셜로 풀었을 때의 풀이입니다.

from collections import defaultdict 
import sys

#지역의 개수 n (1 ≤ n ≤ 100) / 예은이의 수색범위 m (1 ≤ m ≤ 15) / 길의 개수 r 
n,m,r = map(int,sys.stdin.readline().rstrip().split())
# 지역 간 간선 담아주는 사전
relation = defaultdict(list)
# 지역별 아이템 갯수 : 1번 지역~n번 지역 맞춰줄라고 맨 앞에 0 넣음
item_per_area = [0]+list(map(int,sys.stdin.readline().rstrip().split())) 
# 기록
min_road = [ list (int(1e9) for _ in range(n+1)) for _ in range(n+1)]
# 자기에서 자신 가는 것은 0으로 초기화
for self in range(1,n+1) : 
    min_road[self][self] = 0 

for i in range(r) : 
    a,b,l = map(int,sys.stdin.readline().rstrip().split())
    # 가장 적은 길이의 연결 노드 순으로
    min_road[a][b] = min(l, min_road[a][b])
    min_road[b][a] = min(l, min_road[b][a])

def flaud() : 
    new_road = [ list (int(1e9) for _ in range(n+1)) for _ in range(n+1)]
    for k in range(1,n+1) : 
        for i in range(1,n+1) :
            for j in range(1,n+1) : 
                min_road[i][j] = min(min_road[i][j], min_road[i][k] + min_road[k][j])

# 플로이드 워셜 시행
flaud()
# 아이템 총 갯수
answer_items = 0
# 각 지역마다 돌면서 각 지역의 아이템 총 합 알아내기 
for now_area in range(1,n+1) : 
    tmp_items = 0
    for next_area in range(1,n+1) : 
        if min_road[now_area][next_area]<=m : 
            tmp_items+=item_per_area[next_area]
    answer_items = max(answer_items, tmp_items)

print(answer_items)

• 플로이드 워셜은 미리 무한대 이차원 배열을 선언해둬야 합니다.
• 자기자신 -> 자기자신을 0으로 초기화해둬야 합니다.

< 내 틀렸던 풀이, 문제점>

<9프로 틀린 풀이>

from collections import defaultdict, deque
import heapq
import sys
# 최단 비용인데 원래는,, 최대 비용으로 다익스트라 구성하면 되겠다.

#지역의 개수 n (1 ≤ n ≤ 100) / 예은이의 수색범위 m (1 ≤ m ≤ 15) / 길의 개수 r 
n,m,r = map(int,sys.stdin.readline().rstrip().split())
relation = defaultdict(list)

# 지역별 아이템 갯수 : 1번 지역~n번 지역 맞춰줄라고 맨 앞에 0 넣음
item_per_area = [0]+list(map(int,sys.stdin.readline().rstrip().split())) 

max_item = [ it for it in item_per_area ] # 1부터 n개의 지역
for i in range(r) : 
    a,b,l = map(int,sys.stdin.readline().rstrip().split())
    # 가장 적은 길이의 연결 노드 순으로
    heapq.heappush(relation[a],((l,b)))
    heapq.heappush(relation[b],((l,a)))

# 예은이가 얻을 수 있는 최대 아이템 개수를 출력한다.
# 각 지역마다 떨어뜨린 후 얻을 수 있는 최대 아이템 개수
def dik(start_area) : 
    q = deque()
    visit = [0 for _ in range(n+1)]
    result_item = 0
    q.append((start_area, 0)) # 현재 노드 /  길의 길이
    visit[start_area] = 1
    
    while q :  
        now_area, now_length = q.popleft()
        for next_length, next_area in relation[now_area] : 
            if visit[next_area] == 0 : 
                if now_length+next_length>m : 
                    continue
                visit[next_area] = 1
                q.append((next_area, now_length+next_length))
    
    for visit_area in range(1,n+1) : # 방문한 장소의 아이템 득템
        if visit[visit_area] == 1 :
            result_item+=item_per_area[visit_area]
    return result_item

answer = 0

for area in range(1,n+1) :
    answer = max(answer, dik(area))

print(answer)

• 오늘 스터디원분들의 풀이를 보았는데 각 지역까지의 최단 거리를 구하면 되는 거였습니다.
• 최단 거리를 구현하는 것으로 풀이를 변경하겠습니다.

<반성 점>

• 최단 거리를 이용해서 풀 수 있는 문제일 거라고는 생각하지 못했습니다.

<배운 점>