[python] SWEA - 1868. 파핑파핑 지뢰찾기

문제 해결

1. D4 | BFS

2. 클릭이 가능한 부분('.')을 찾아서 클릭을 할지 말지 결정한다

 (1) 주변(8방향)에 지뢰가 한개도 없다면 클릭!

 (2) 하나라도 있으면 건너 뛴다

3. 클릭을 했다면 그 지점의 주변에 지뢰가 아닌부분을 가지고 BFS탐색을 한다.

 (1) 주변지점을 기준으로 또 그주변에 지뢰가 없으면 계속 퍼져나가면서 탐색한다

 (2) 지뢰가 하나라도 있으면 그 지점은 더 나아가지 못한다.

4. 클릭 했을 때 마다 카운트를 세어주고

5. 나머지 클릭이 안된부분을 찾아서 더해주면 끝

 

💨 처음에 주변에 지뢰가 하나도 없는 지점을 다 찾아놓고 시작하려 했지만 시간이 오래걸릴 거 같아 찾으면서 가는 방식을 선택했다. 다 풀고보니 그렇게 해도 될거같다.

 

소스 코드

from _collections import deque


# 주변에 지뢰가 하나도 없으면 클릭하고 하나라도 있으면 클릭하지 않고 건너 뛴다.
def clickOrNot(x, y):
    global cnt
    next_target = []
    for k in range(8):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < n and 0 <= ny < n:
            if mine[nx][ny] == '.':
                next_target.append((nx, ny))
            elif mine[nx][ny] == '*':
                break
    else:
        # 지뢰가 주변에 하나도 없어 else문으로 오게 되면
        if next_target: # 이 때 주변으로 갈 수 있는 경우가 있으면(next_target에 값이 존재하면)
            mine[x][y] = 'o'  # 체크했다는 표시를 해주고
            cnt += 1 # 클릭 횟수를 더해주고
            spread(next_target) # 주변으로 퍼져나간다


def spread(lst):
    q = deque(lst)
    while q:
        x, y = q.popleft()
        mine[x][y] = 'o'  # 위 함수의 경우와 다르게 클릭해서 주변으로 퍼졌으므로 일단 체크가 되고
        next_next_target = []
        for k in range(8):  # 8방향 탐색
            nx = x + dx[k]
            ny = y + dy[k]
            if 0 <= nx < n and 0 <= ny < n:
                if mine[nx][ny] == '.':
                    next_next_target.append((nx, ny))
                elif mine[nx][ny] == '*':
                    break
        else:
            # 주변에 지뢰가 없으면 또 다시 퍼져 나간다.
            spread(next_next_target)


# 클릭해도 퍼져나가지 않는 곳
def restTarget():
    global cnt
    for i in range(n):
        for j in range(n):
            if mine[i][j] == '.':
                cnt += 1


for tc in range(1, 1 + int(input())):
    n = int(input())
    mine = [list(input()) for _ in range(n)]
    cnt = 0
    # 8방향 탐색
    dx, dy = [-1, -1, -1, 0, 1, 1, 1, 0], [-1, 0, 1, 1, 1, 0, -1, -1]  # 좌상부터 시계방향
    # 클릭 할 수 있는 부분('.')을 찾아서 최초 클릭을 할지 말지 정한다.
    for i in range(n):
        for j in range(n):
            if mine[i][j] == '.':
                clickOrNot(i, j)

    restTarget()
    print('#{} {}'.format(tc, cnt))

 

출처: SW Expert Academy

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc&categoryId=AV5LwsHaD1MDFAXc&categoryType=CODE

SW Expert Academy

‘파핑 파핑 지뢰 찾기’라는 유명한 게임이 있다. 이 게임은 RXC 크기의 표를 이용하는 게임인데, 표의 각 칸에는 지뢰가 있을 수도 있고 없을 수도 있다. 표의 각 칸을 클릭했을 때, 그 칸이 지뢰가 있는 칸이라면 ‘파핑 파핑!’이라는 소리와 함께 게임은 끝난다. 지뢰가 없는 칸이라면 변이 맞닿아 있거나 꼭지점이 맞닿아 있는 최대 8칸에 대해 몇 개의 지뢰가 있는지가 0에서 8사이의 숫자로 클릭한 칸에 표시된다. 만약 이 숫자가 0이라면 근처의 8방향에 지뢰가 없다는 것이 확정된 것이기 때문에 그 8방향의 칸도 자동으로 숫자를 표시해 준다. 실제 게임에서는 어떤 위치에 지뢰가 있는지 알 수 없지만, 이 문제에서는 특별히 알 수 있다고 하자. 지뢰를 ‘*’로, 지뢰가 없는 칸을 ‘.’로, 클릭한 지뢰가 없는 칸을 ‘c’로 나타냈을 때 표가 어떻게 변화되는지 나타낸다.     세 번째 예에서는 0으로 표시 될 칸들과 이와 인접한 칸들이 한 번의 클릭에 연쇄적으로 숫자가 표시된 것을 볼 수 있다. 파핑 파핑 지뢰 찾기를 할 때 표의 크기와 표가 주어질 때, 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야 하는지 구하는 프로그램을 작성하라. [입력] 첫 번째 줄에 테스트 케이스의 수 T가 주어진다. 각 테스트 케이스의 첫 번째 줄에 하나의 정수 N(1 ≤ N ≤ 300) 이 주어진다. 이는 지뢰 찾기를 하는 표의 크기가 N*N임을 나타낸다. 다음 N개의 줄의 i번째 줄에는 길이가 N인 문자열이 주어진다. 이 중 j번째 문자는 표에서 i번째 행 j번째 열에 있는 칸이 지뢰가 있는 칸인지 아닌지를 나타낸다. ‘*’이면 지뢰가 있다는 뜻이고, ‘.’이면 지뢰가 없다는 뜻이다. ‘*’와 ‘.’외의 다른 문자는 입력으로 주어지지 않는다. [출력] 각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 최소 몇 번의 클릭을 해야 지뢰가 없는 모든 칸에 숫자가 표시될 것인지 출력한다.