백준(BOJ) 18809번 Gaaaaaaaaaarden

문제 : https://www.acmicpc.net/problem/18809

18809번: Gaaaaaaaaaarden

 

풀이 :

 

loc 배열에는 0과 g에 개수만큼 1이, r에 개수만큼 2가 들어있다. 이 loc 배열을 next_permutation을 통해 어느 좌표에 g

 

와 r을 넣어야 하는지에 대한 모든 경우의 수를 돌려볼 수가 있다. g와 r을 넣을 수 있는 cand 좌표 벡터를 만든 후 g와 r

 

에 위치를 큐에 집어넣었다면 꽃의 개수를 찾는다.

 

꽃의 개수를 찾을 때에는 st pair 2차원 벡터를 통해 { 현재시간, 어떤 색깔 } 찾게 되며

 

색깔이 없다면 방문할 수 있는 곳이며 큐에 넣어주고

 

색깔이 이미 있다면 현재시간과 지금 들어온 색깔을 비교해 꽃이 될 수 있는지 확인한다.

 

이미 꽃이 된 좌표는 큐에서 꺼낼 때 무시한다.  st[y][x].second == 3인 경우 

 

코드 ( C++ )