소가 길을 건너간 이유 6
-
[Python] 백준 14466 소가 길을 건너간 이유 6알고리즘/문제풀이 2021. 7. 24. 19:32
1. 문제 링크 14466번: 소가 길을 건너간 이유 6 14466번: 소가 길을 건너간 이유 6 첫 줄에 N, K, R이 주어진다. 다음 R줄에는 한 줄에 하나씩 길이 주어진다. 길은 상하좌우로 인접한 두 목초지를 잇고, r c r′ c′의 형태 (행, 열, 행, 열)로 주어진다. 각 수는 1 이상 N 이하이다. www.acmicpc.net 2. 문제 요약 길을 이용해야 하는 소들 쌍을 구하는 문제 예제 문제를 그려보면 아래와 같다. 소의 위치와 길의 위치가 주어지고, 두 소가 쌍을 지어 서로 길 없이 만날 수 있는지 확인을 해야 한다. 3. 아이디어 정리 소를 한 마리씩 돌려주면서(소 1) 정해진 길 없이 길을 건널 때 방문 여부를 모두 체크 ⇒ bfs 1에서 구한 소 1의 방문 여부 결과에서 소 2..