문제
N×N 격자에 지뢰가 숫자(1~9, 해당 칸의 지뢰 개수)로 표시되어 있다. 지뢰가 없는 칸에 인접한 8칸의 지뢰 합을 표시하라. 합이 10 이상이면 M, 지뢰 칸은 *, 0이면 0을 출력한다.
입력
첫째 줄에 N, 이후 N줄에 격자가 주어진다 (.은 빈 칸, 숫자는 지뢰 수).
출력
각 칸의 결과를 출력한다.
예제
| 입력 | 출력 |
|---|---|
3 1.1 ... 2.2 | *1* 232 *2* |
풀이
각 지뢰 칸의 값을 인접 8칸에 누적하고, 합이 10 이상이면 M으로 표시한다.
- 격자를 순회하며 숫자가 있는 칸(지뢰)을 찾는다
- 해당 칸을
*로 표시하고, 인접 8칸에 지뢰 개수를 더한다 - 이미 지뢰(
*)이거나 이미M인 칸은 건너뛴다 - 누적합이 10 이상이 되면
M으로 표시한다
핵심 아이디어: 각 지뢰의 영향을 주변 칸에 누적하는 방식으로, 한 칸에 여러 지뢰의 영향이 합산된다.
코드
import sys
N = int(sys.stdin.readline())
mine_map = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
row = sys.stdin.readline().rstrip()
for j in range(N):
col = row[j]
if col == ".":
continue
mine_count = int(col)
mine_map[i][j] = "*"
k = 0 if i - 1 < 0 else i - 1
l = N - 1 if N <= i + 1 else i + 1
m = 0 if j - 1 < 0 else j - 1
n = N - 1 if N <= j + 1 else j + 1
for o in range(k, l + 1):
for p in range(m, n + 1):
area = mine_map[o][p]
if area == "*" or area == "M":
continue
if 10 <= area + mine_count:
mine_map[o][p] = "M"
else:
mine_map[o][p] += mine_count
for map_row in mine_map:
print("".join(map(str, map_row)))복잡도
- 시간: O(N²) — 격자 전체 순회, 지뢰당 인접 8칸 처리
- 공간: O(N²) — N×N 격자 배열