백준_28360_양동이 게임(python)

★ 접근

 - 문제 + 입력 + 예제 입력을 미루어 보았을 때 그래프 이론을 떠올렸고 dfs로 풀었다가 반례를 찾아서 bfs로 풀었다가 반례를 못 찾아서 알고리즘 분류를 보고 dp로 풀었다. 그래프 문제인데도 불구하고 dp로 풀 수 있는 이유는 물은 무조건 번호가 작은 양동이 => 번호가 큰 양동이로 흘러간다는 조건이 있기 때문에 dp로 풀 수 있는 것 같다.

※ bfs로도 풀 수 있지만 bfs로 풀면 + 위상정렬을 같이 사용해야 해서 문제 난이도가 골드 1 ~ 2 수준으로 올라간다고 한다.

★ 풀이

 1. 물의 양을 기록해놓을 dp 테이블을 만들고 1번 양동이를 100으로 초기화 해 놓은다.

 2. 물은 무조건 작은 양동이에서 큰 양동이로 흘러가니가 가장 바깥 for문을 1번부터 n+1까지 해놓은다.

 3. 해당 양동이에 연결된 호스의 개수가 0 이상이면 물을 나눠주고 0이면 answer에 물 양을 저장해놓는다.

 4. 양동이에 가장 많이 저장된 물의 양을 출력한다.

 

★ 코드

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    v,w = map(int,input().split())
    graph[v].append(w)
dp = [0] * (n+1)
dp[1] = 100
answer = []
for i in range(1,n+1):
    if len(graph[i]) > 0:
        for j in graph[i]:
            dp[j] += dp[i] / len(graph[i])
    else:
        answer.append(dp[i])
print(max(answer))

★ 회고

  최근 그래프 문제인데도 불구하고 dfs, bfs를 사용하지 않는 또는 dfs와 bfs가 주가 아닌 유형이 많아지는 것 같다.

조건을 잘 읽어서 타개해보자!!