백준 14466 소가 길을 건너간 이유6 c++

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

14466번: 소가 길을 건너간 이유 6

오랜만에 알고리즘 문제를 풀었습니다 ㅎㅎ 이제 자기 전에 한 문제씩 다시 풀어야겠습니다...

 

길이 연결되어 있는 상황에서 길을 건너지 않고는 못 만나는 소가 몇 쌍인지 구하는 문제입니다.

 

반대로 생각하면 전체 경우인 kC2 에서 길을 안 건너고 만날 수 있는 경우를 빼면 됩니다.

 

조합으로 구하기 위해 소 번호는 자신보다 큰 소를 만날 때만 카운트합니다. (벡터에 넣습니다.)

 

bfs를 이용해서 이동하고자 하는 다음 칸이 길을 통해서 가는 거면 못 가는 걸로 생각하면 됩니다.

 

코드는 다음과 같습니다.