구현(지뢰 찾기/S5)

1. 문제

다들 windows에서 지원하는 지뢰 찾기 게임을 한번쯤은 해 보았을 것이다. 특히 동호는 지뢰찾기의 매니아로 알려져 있다. 지뢰 찾기 map은 N*N의 정사각형 모양으로 각 칸에는 숫자가 들어가 있거나 지뢰가 들어가 있다. 빈 칸에는 숫자 0이 들어있다고 생각하자.

map의 어떤 칸에 적혀 있는 숫자는, 그 칸과 인접해 있는 여덟 개의 칸 중에서 지뢰가 들어 있는 칸이 몇 개인지를 나타내 준다. 물론 인접한 칸이 map 내부에 있는 경우에 대해서만 생각하면 된다. 예제를 보면 더 잘 이해할 수 있을 것이다.

이번 문제는 조금 업그레이드 된 지뢰 찾기로, 한 칸에 한 개의 지뢰가 있는 것이 아니고, 한 칸에 여러 개(1 이상 9 이하)의 지뢰가 묻혀 있는 게임이다. 따라서 map의 어떤 칸에 적혀 있는 숫자는, 그 칸과 인접해 있는 여덟 개의 칸들에 들어 있는 지뢰의 총 개수가 된다.

이미 windows 지뢰찾기 같은 것을 마스터한 영식이는, map에서 지뢰에 대한 정보만이 주어졌을 때, 영식이는 map을 완성하고 싶다고 한다. N과 지뢰의 위치가 주어졌을 때, 영식이를 도와서 지뢰 찾기 map을 완성하는 프로그램을 작성하시오.

 

2. 입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 N개의 줄에는 지뢰 찾기 map에 대한 정보가 주어지는데 '.' 또는 숫자로 이루어진 문자열이 들어온다. '.'는 지뢰가 없는 것이고 숫자는 지뢰가 있는 경우로 그 칸의 지뢰의 개수이다. 한 줄은 N개의 문자로 이루어져 있다.

5
1....
..3..
.....
.4...
...9.

 

3. 출력

N개의 줄에 걸쳐서 완성된 지뢰 찾기 map을 출력한다. 지뢰는 '*'로 출력하며. 10 이상인 경우는 'M'(Many)으로 출력하면 된다. map은 숫자 또는 'M' 또는 '*'로만 이루어져 있어야 한다.

*4330
14*30
47730
4*M99
44M*9

 

4. 코드

import sys

n = int(sys.stdin.readline().strip())
bombList =[list(map(str, sys.stdin.readline().strip())) for _ in range(n)]

# 0으로 된 2차원 배열 생성
result = [['0' for y in range(n)] for x in range(n)]

# 지뢰를 둘러싼 좌표를 계산하기 위한 값
aRound = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

for i in range(0,n):
  for j in range(0,n):
    # 숫자가 나오면 지뢰라고 판단
    if bombList[i][j] != '.':
      result[i][j] = '*'
      # 지뢰를 둘러싼 좌표 8개에 지뢰값을 추가한다.
      for a in aRound:
        # 좌표 계산
        x, y = i + a[0], j + a[1]
        if x >= 0 and x < n and y >= 0 and y < n:
          if result[x][y] != '*' and result[x][y] != 'M':
            result[x][y] = str(int(result[x][y]) + int(bombList[i][j]))
            # 값이 10이사이면 문자 'M'을 대입
            if int(result[x][y]) >= 10:
              result[x][y] = 'M'

# 결과값 출력
for b in result:
  for r in b:
    print(r,end='')
  print()

 

5. 풀이설명

① 입력받은 2차원 배열과 크기가 같은 0으로 된 결과값 배열을 생성한다.

 

② 지뢰를 둘러싼 8개의 배열 좌표를 계산하기 위한 리스트를 생성한다.

 

③ 반복문 실행 시 입력값이 '.'이 나오면 같은 인덱스의 결과값 배열에 '*'문자를 대입한다.

 

④ ②에서 생성한 배열을 통해 지뢰를 둘러싼 배열의 좌표를 계산한다.

 

⑤ ④에서 계산한 좌표가 0보다 크더나 같고 입력받은 n보다 작으면 입력박은 지뢰값만큼 결과값배열에 추가한다.

 

⑥ 결과값이 10이 넘어가면 M을 대입하고 해당값은 ⑤ 로직을 타지 않는다.

 

⑦ 결과값 배열을 문자열 형태로 변환하여 출력한다.

 

6. 느낀점

처음 제출시에 지뢰 주위를 둘러싼 배열을 미리 계산하지 않고 중간마다 계속 좌표를 계사해서 시간 초과로 실패했다. 풀이설명 ④의 로직을 추가하니 성공이 나왔는데 입력받은 수를 정수로 받고 문자를 특정 숫자로 치환하여 숫자 형태로 로직을 처리하면 1000초 정도 시간이 단축되는 것을 확인했다.(다만 위 코드가 보기에는 더 편하다.)