백준 17412번 문제입니다.
📕 문제
N개의 도시가 P개의 단방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 가며 워해머를 한다. 성실한 이석원은 1번에서 2번으로 가는 서로 다른 경로를 최대한 많이 찾으려고 하는데, 이때 한 경로에 포함된 길이 다른 경로에 포함되면 안된다. 입력에는 1번 도시와 2번 도시를 연결하는 길은 없다. 도시의 번호는 1번부터 N번까지이다.
입력
첫째 줄에 두 정수 N(3 ≤ N ≤ 400), P(1 ≤ P ≤ 10,000)이 주어진다. 다음 P개의 줄에는 각 길이 연결하는 출발 도시와 도착 도시의 번호가 주어지며, 두 번호는 다르다.
출력
1번에서 2번으로 가는 서로 다른 경로의 최대 개수를 출력한다.
🔐 풀이
💡 algorithm
Network flow 문제이다. 이 알고리즘의 문제를 많이 풀어보지 않아서 익숙하지는 않지만, 유형만 파악하면 그리 어렵지 않게 풀 수 있다.
.. .+ 추가예정..
👩🏻💻 code
영어 공부 하기 싫어서 알고리즘을 풀었는데 기분이 죠아...
𝑯𝒐𝒏𝒆𝒔𝒕𝒚 𝑰𝒏𝒕𝒆𝒈𝒓𝒊𝒕𝒚 𝑬𝒙𝒄𝒆𝒍𝒍𝒆𝒏𝒄𝒆