[Python] 백준 9082번 지뢰찾기

문제

https://www.acmicpc.net/problem/9082

입력

• 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 첫 줄에 배열의 크기 N(1 ≤ N ≤ 100)이 주어지고, 그 다음 두 줄에 걸쳐서 배열이 주어진다. 
• 첫 줄에는 항상 숫자만이 나타나며 이 숫자들 사이에 공백은 없으며, 둘째 줄에 주어지는 입력들 사이에도 공백은 없다. 그리고 이 숫자들은 올바른 값만이 입력으로 들어온다(지뢰의 위치에 대해 불가능한 값은 입력으로 주지 않는다).

출력

• 각 테스트 케이스에 대해서 주어진 배열에 있는 모든 지뢰의 수를 한 줄에 하나씩 출력한다. 지뢰의 수가 여럿이 될 수 있으면 가능한 지뢰의 수 중 최댓값을 출력한다.

입력 예제

2
5
11122
####*
5
23321
#####

출력 예제

3
4

문제 풀이

• 현재의 인덱스, 왼쪽, 오른쪽에 있는 지뢰를 기반으로 설치 된 지뢰를 찾는 문제이다.
• 확정된 지뢰 *가 있다면 result값을 +1하고, 확정되지 않은 지뢰가 있다면, 현재의 자리에서 찾을 수 있는 지뢰를 모두 탐색해야한다.
  • 왼쪽부터 탐색을 시작할 경우 확정된 지뢰가 오른쪽 끝에 있고, 탐색할 지뢰수가 1인경우 예외가 발생한다. 따라서 !!꼭!! 오른쪽부터 탐색을 진행해야한다. 또한, 탐색해야할 지뢰가 0이 된다면 탐색을 멈춰야한다.
• 이미 확정된 지뢰들을 result값에 할당했다면, [1][0] ~ [1][n]까지 탐색을 진행해야한다.
  • 이 때 #과 *으로 나눠서 탐색을 진행한다.
  • * : 지뢰가 있는 곳이므로 현재 자리에서 탐색해야하는 지뢰 - 1을 진행한다. -> result는 이미 한번에 계산했으므로 result값을 증가시킬 필요는 없다.
  • # : 지뢰가 있는지 없는지 확실하지 않은 곳이므로 오른쪽부터 탐색을 진행한다. 탐색할 자리가 범위 내에 있고, 탐색해야할 지뢰가 남아있다면 result + 1, tmp - 1을 진행한다.
• 위 과정을 마치면 result 값에 탐색된 모든 지뢰가 계산되어있다.

코드

t = int(input())
for tc in range(t):
    bomb = []
    result = 0
    n = int(input())
    for _ in range(2):
        bomb.append(input())

    # 확정된 지뢰 '*' 더하기
    for i in range(n):
        if bomb[1][i] == '*':
            result += 1

    # 각 자리에 있을 수 있는 지뢰 수 탐색
    for i in range(n):
        if '0' < bomb[0][i] <= '9':
            tmp = int(bomb[0][i])
        else:
            continue

        # 확정된 지뢰가 있다면 탐색 해야할 지뢰 수 -1
        for j in (1, 0, -1):
            y = 1
            x = i + j

            # 더 이상 탐색 해야할 지뢰가 없다면 탐색 종료
            if tmp == 0:
                break

            if 0 <= x < n and bomb[y][x] == '*':
                tmp -= 1

        # 확정되지 않은 지뢰 탐색
        for j in (1, 0, -1):
            y = 1
            x = i + j

            if tmp == 0:
                break

            # 확정된 지뢰 배열 내부에서 수정
            if 0 <= x < n and bomb[y][x] == '#':
                bomb[1] = bomb[1][:x] + '*' + bomb[1][x + 1:]
                result += 1
                tmp -= 1

    print(result)