18809 Gaaaaaaaaaarden

18809 Gaaaaaaaaaarden

www.acmicpc.net/problem/18809

1.접근

초록색과 빨간색 조합을 써야하므로 itertools 모듈에 combination을 써주고

경우의 수가 너무 많으므로 백트래킹을 활용한 BFS로 최대 꽃개수를 구해보자

2.풀이

combination을 사용해서 해볼 경우의수를 모두 BFS함수에 넣는다.

BFS를 초록색을 돌리는 큐와 빨강색을 돌리는 두개의 큐로 나눠서 풀었다.

우선 방문한곳을 체크하는 visited함수를 -1로 초기화하고 몇번째날에 들어가는지(cnt)로 갱신한다.

우선 초록색을 돌리면

큐에서 꺼낸좌표가 flower이면 continue

좌표가 n,m범위에 있고 바다가 아니며 visited가 -1이면 언제 방문했는지 visited에 cnt를 넣어주고 큐에도 넣어준다.

다음으로 빨강색을 돌린다

n,m범위에있고 바다가 아닐때 visited가 -1인지 visited가 현재 cnt와 같은지 확인해 주어야한다

만약cnt가 같다면 flower값을 증가시켜주고 큐에는 넣지않는다 (꽃이피면 퍼지지않으므로)

만약-1이라면 방문했었다는 뜻으로 -2로 값을 바꿔주고 큐에 넣는다.

3.코드

4.배운점

• 오늘 bfs두문제를 풀었는데 변수가 많이 필요한 문제에서 지역변수와 전역변수 for문의 i,j등이 겹치게 푸는 실수를해서 시간을 많이 잡아먹었다. 코드 보기도 불편하고 하니 조금 귀찮더라도 변수를 알아보기 쉽게 _를 써서 표현하는 습관을 갖자

• 처음 GQ와 RQ를 전역변수로 선언하고 문제를 풀어서 while GQ and RQ 에서 왜 틀렸는지 알아내기 힘들었다. 둘중 하나는 남아있는데 전역변수라 큐에 계속 담겨있는 상태로 다음 bfs로 이어졌기 때문이다. 지역변수를 쓰는 습관을 기르자. 그래도 하나씩 해보며 찾아서 뿌듯했다.