티스토리 뷰
문제링크
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
풀이
풀이방법
지뢰가 있는 칸을 알고있다는 전제하에 최소한의 클릭으로 지뢰찾기 게임을 클리어하는 문제입니다.
칸의 숫자가 0이라면 주변 8칸의 숫자가 저절로 표시되고 그 칸에 0이 있다면 연속해서 8칸의 숫자가 표시되는 규칙이 있습니다.
이를 이용하면 최소 몇번의 클릭으로 클리어할 수 있는지 알 수 있습니다.
알고리즘은 다음과 같은 과정으로 진행됩니다.
1. board의 (0, 0) 좌표부터 검사를 시작합니다.
2. 주변에 지뢰가 없는 칸인 경우, 해당 칸의 값을 0으로 바꿔주고 클릭횟수를 증가시킵니다.
3. 해당 칸의 주변칸도 숫자를 표시해줍니다.
4. 표시된 숫자가 0이라면 그 칸의 주변 숫자도 표시해줍니다.
5. board의 모든 칸에 대한 검사를 마치고 난 뒤 다시 board에서 .의 개수를 세어주고 클릭 횟수에 더해줍니다.
board에서 특정 칸의 값이 0인 경우 그 주변의 칸에 대한 숫자를 표시하는 알고리즘에서 DFS 알고리즘을 사용하여
주변 칸의 숫자가 0인경우에도 연쇄적으로 숫자를 표시해주도록 했습니다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] 백준 2869 (0) | 2019.11.17 |
|---|---|
| [알고리즘] SWEA 2806 N-Queen (0) | 2019.11.02 |
| [알고리즘] 백준 13460 (1) | 2019.10.13 |
| [알고리즘] 백준 2309 (0) | 2019.10.05 |
댓글