백준 - 2565번(DP,BFS)

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

import sys
from collections import deque

n = int(sys.stdin.readline())

q = deque([])
arr = []

for _ in range(n):
    a,b = map(int,sys.stdin.readline().split())
    q.append([a,b,1])
    arr.append([a,b])

ans = 0
while q:
    x,y,cnt = q.popleft()
    if cnt > ans:
        ans = cnt

    for i in arr:
        if ((i[0]> x and i[1] >= y) or (i[0] >= x and i[1] > y)) and [i[0],i[1],cnt+1] not in q:
            q.append([i[0],i[1],cnt+1])

print(n-ans)

특정 DP문제는 BFS와 유사한 방식으로 풀이가 가능하다. 특정 조건만 잘 생각해주면 된다.

모든 분기점(여기서는 처음 q에 담기는 cnt가 1일 때의 경우들) 직전에 담긴 출발지점과 도착지점이 크거나 같은 경우만 다음에 올 수 있다.

근데 둘다 같으면 계속 본인의 값이 들어가기 때문에 무한루프에 빠지기 때문에 or을 이용해서 구분해준다. 그렇게 cnt를 1씩 증가해주면서 cnt가 가장 클 때가 조건에 맞게 최대한 많은 수의 전선을 연결할 수 있는 경우다. 이를 n에서 빼주면 답이 된다.

사실 DP치고 굉장히 친절한 문제다. DP문제를 시험에서 만났을 때 가장 어려운 점은 다음과 같다.

1. 이게 DP문제 인가?

2. 이게 DP문제라면 점화식을 세워서 풀어야 하나 or bfs로 분기점을 나눠 조건에 따라 누적으로 전체 탐색을 해야 하나.

3. 이걸 어떻게 구현하나.

 

보통 1번에서 시간을 많이 잡아먹는다.. 방법은 dp 문제를 더 많이 풀어보는 수밖에...