Problem Check

요구 사항 정리

• 크기의 격자판이 있습니다. 총 개의 칸이 있으며, 구름이 있는 칸과 없는 칸으로 구분할 수 있습니다.
• 개의 칸을 모두 순회하면서, 구름이 없는 칸 주변에 있는 모든 구름의 개수를 세고, 그 값이 인 칸의 수를 구하면 됩니다.

알고리즘 정리

• 완전 탐색 알고리즘을 사용하는 문제입니다.
• 시간복잡도는 입니다.

Problem Solving

주어지는 게임판의 정보를 2차원 배열에 저장하고, 모든 칸을 하나씩 살펴봅니다. 구름이 있는 칸에는 깃발이 존재하지 않으므로, 칸에 적힌 문자가 0인 칸을 만날 떄마다 주변 8칸을 탐색하여 구름의 개수를 세면 됩니다.

2차원 배열에서 주변에 인접한 칸을 탐색할 때는 보통  기법을 사용합니다. 이 기법은 이 문제 뿐만 아니라 2차원 배열에서의 dfs, bfs 등의 유형에서도 유용하게 사용할 수 있으니 익혀두면 많은 도움이 될 것입니다.

먼저, 따로  기법 없이 임의의 위치 에 있는 칸 를 기준으로 상하좌우 4방향 탐색을 구현한다고 생각해봅시다. 우리는 아래 4개의 위치를 고려해야 합니다.