[Python] 백준 18809 Gaaaaaaaaaarden

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

18809번: Gaaaaaaaaaarden

1. 접근 방법

좀 귀찮은 구현 문제라고 생각했는데, 구현보다는 브르투포스+BFS의 느낌이 컸다.

조합은 itertools로 간단하게 구현했는데, 세부 구현에서 고민을 했다.

 

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/baekjoon_py/blob/master/18000/18809.py

GitHub - mintropy/baekjoon_py: BOJ를 Python으로 해결한 코드의 저장소입니다.

📕코드 해설

itertools.combinations으로 가능한 땅 위치에서 조합을 찾았다. 조합을 찾는 방법은 여러 가지 있을 텐데, 가능한 모든 땅에서 R + G만큼의 땅의 조합을 찾고, 거기서 R 또는 G의 조합을 찾는 게 빠른 것 같다.

가능한 땅에서 R만큼의 땅의 조합을 찾고, 남은 땅마다 G만큼의 조합을 찾는 방법으로 했을때는 상대적으로 느리게 나왔다.

 

각 배양액이 뿌려졌을 때, BFS구현은 간단하지만, 한가지 주의해야 할 부분은 한 단계씩 진행해야 한다는 것이다.

한 단계를 모두 거치고, 빨강, 초록 배양액이 같은 땅에 위치할 수 있는지 확인하고 넘어가는 작업이 필수적이다.

이 작업을 하기위해 다양한 방법이 있지만, 나는 내부에 deque를 두고 사용했다. 제출하고 보니 그냥 list로 사용했으면 조금이나마 더 빠르게 해결할 수 있었을 것 같다.

그리고 탐색 과정에서도 1, 2번인 땅에서만 퍼지게 하는 방법도 있지만, 다른 방법으로 할 때 꽃이 피었는 것에 대한 확인도 꼭 해야 한다.

 

3. 생각 정리

Python3으로는 시간적으로 빠듯한 느낌이 있다.

그리고, 파이썬의 type hint를 적극적으로 사용해보려 하다가, List[List] 형태의 힌트를 기입했다.

Python3에서는 정상적으로 작동했지만, pypy3에서는 아직 지원하지 않는 것인지 에러가 발생했고, 타입 힌트 없는 상태로 통과했다. 다른 방법으로 적용하면 되는지는 잘 모르겠지만, pypy 보다는 Python을 사용하기 때문에 큰 문제라 생각하지는 않는다.