[python] 백준 9082 지뢰찾기

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

9082번: 지뢰찾기

 

 

문제해결

상당히 복잡해 보이지만 한 번 이해하면 간단하다.

우선 지뢰가 확실히 있는 곳을 통해 블록의 주위에 개수가 몇개 있는지를 최신화 한다.

그리고 왼쪽부터 오른쪽으로 가면서 블록주위 숫자가 모두 숫자가 0이 아니면 1개를 추가하고 블록의 주위 개수를 1씩 줄여주면 된다.

 

CODE

t = int(input())
for _ in range(t):
    n = int(input())
    graph = []
    graph.append([int(c) for c in str(input()).rstrip()])
    graph.append([c for c in input().rstrip()])
    ans = 0
    for x in range(n):
        if graph[1][x] == '*':
            graph[0][x] -= 1
            ans += 1
            if x<n-1:
                graph[0][x+1] -= 1
            if x>0:
                graph[0][x-1] -= 1
    if graph[1][0] =='#' and graph[0][0] !=0 and graph[0][1] !=0:
        ans += 1
        graph[0][0] -= 1
        graph[0][1] -= 1
    for x in range(1,n-1):
        if graph[1][x] == '#':
            if graph[0][x-1] >= 1 and graph[0][x] >= 1 and graph[0][x+1] >=1:
                graph[0][x-1] -=1
                graph[0][x] -= 1
                graph[0][x+1] -= 1
                ans +=1
    if graph[1][n-1] =='#' and graph[0][n-1] !=0 and graph[0][n-2] !=0:
        ans += 1
        graph[0][n-1] -= 1
        graph[0][n-2] -= 1
    print(ans)

 코드를 보고 의문이 들 사람도 있을 것이다.

 

이것이 정답인 테스트 케이스가 있는데

아래의 코드를 보면

이렇게 정답 계산되는데 괜찮나요?

답은

괜찮다!

 

그림을 보면 알 것이다.

밀어준다는 생각을 하면 되고

정답은 변함이 없다!

이 생각을 하고나면 지뢰찾기 문제는 편하게 풀 것이다.