[Python] 백준 9082번 - 지뢰 찾기

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

9082번: 지뢰찾기

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 다이나믹 프로그래밍(DP)
 - 애드 혹

문제

지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타낸다. 지뢰가 확실히 있는 위치를 *, 숨겨진 블록을 #으로 표시한다. 첫째 줄에는 숫자만 나타나고 둘째 줄에는 *와 #만 나타나는데, 지뢰는 둘째 줄에만 있다.

12110
##*##

위의 그림 2×5 배열에는 지뢰가 2개가 있다는 것을 알 수 있다. 숨겨진 블록 중 첫 번째 블록에 지뢰가 숨겨져 있고, 나머지 하나는 두 번째 줄의 가운데에 있다.

2×N 배열이 주어지면 주어진 배열에 있는 모든 지뢰의 개수(*까지 포함)를 찾는 프로그램을 작성하시오.

입력

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

출력

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

---

지뢰 찾기 문제라고 하기에

 

쉬울줄 알았다.

 

어려웠다... 그리고 난 결국 풀지 못했고 다른 사람의 코드를 보고 겨우 푼 수준이었다.

 

참고한 블로그

 

https://jaimemin.tistory.com/1000

백준 9082번 지뢰찾기

 

https://velog.io/@jychan99/%EB%B0%B1%EC%A4%80BOJ-9082.-%EC%A7%80%EB%A2%B0%EC%B0%BE%EA%B8%B0-Gold-5

[백준/BOJ] 9082. 지뢰찾기 [Gold 5]

 

---

우선 내가 푼 방식은 위의 첫 번째 블로그 방식을 사용했다.

 

머리를 열심히 싸매봤지만 도저히 방법이 떠오르질 않았고

 

그나마 내가 풀려고 했던 방법과 제일 유사한 방법이 첫번째 블로그 방식이었다.

 

import sys
input = sys.stdin.readline

T = int(input())
for _ in range(T):
    n = int(input())
    num = list(map(int, input().rstrip()))
    mine = input().strip()
    result = 0
    dir = [-1, 0, 1]
    for i in range(n):
        if i == 0:
            if num[0] != 0 and num[1] != 0:
                num[0] -= 1
                num[1] -= 1
                result += 1
        elif i == (n-1):
            if num[i] != 0 and num[i-1] != 0:
                num[i-1] -= 1
                num[i-2] -= 1
                result += 1
        else:
            if num[i-1] != 0 and num[i] != 0 and num[i+1] != 0:
                num[i-1] -= 1
                num[i] -= 1
                num[i+1] -= 1
                result += 1
    print(result)

 

3묶음씩 비교하여

 

0이 있으면 지뢰가 없다는 뜻으로 넘기기

 

0이 없으면 지뢰가 있으니 지뢰 개수 +1