Python으로 푸는 SW Expert Academy 1868. 파핑파핑 지뢰찾기

1868. <파핑파핑 지뢰찾기>는 주변에 지뢰가 없는 경우 연쇄적으로 터지는 지뢰찾기 게임을 구현하는 문제이다.

삼성 SW Expert Academy 문제 리스트 보러 가기

github에서 코드 보기

문제 조건

- 2차배열에서 지뢰가 어디에 있는지 표시('*')되어 있다.

- 지뢰가 없는 칸을 클릭하면, 가로,세로,대각선의 8개의 위치에서 지뢰가 몇 개인지 숫자가 표시된다.

- 클릭한 칸의 주변 지뢰의 수가 0이라면, 연쇄적으로 주변의 칸까지 터질 수 있다. 

(그 주변 칸의 주변 지뢰수가 0이라면 또다시 이 작업을 연쇄적으로 반복한다)

- 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야하는지 구하여야 한다.

문제 이해하기

  : 클릭하는 위치 , *  : 폭탄 위치

기본 예시로 주어진 두가지 테스트 케이스의 클릭 위치는 다음과 같다.

3 ..* ..* **. #1 2		2	*
	2	4	*
	*	*

5 ..*.. ..*.. .*..* .*... .*...  #2 8		2	*	2
	1	3	*	3	1
		*			*
		*	3	1	1
		*	2		0

문제 풀이

문제를 풀기 위해 주어진 2차원 배열을 2번 순회한다.

첫번째 순회에서는, 주변 8면에 지뢰가 없는 위치(원소)를 찾아 그러한 원소들을 우선적으로 깨주기 위해 순회한다. 

주변 8면에 지뢰가 없는 원소가 서로 이어져 있을 경우에는, 그 중에 하나라도 깨면 어차피 연쇄적으로 깨지게 되므로 어떤걸 먼저 깨야하나 고민할 필요가 없다.

2차원 배열을 한번 순회하면서, 아래의 작업을 반복해준다.

1. 주변 8면에 지뢰가 없고, 아직 깨지지 않은 경우(즉, '.' 인 경우)를 먼저 클릭해준다. (이때 클릭 횟수를 센다)

2. 클릭 했다면, 그 주변 원소들에게도 연쇄적으로 클릭한 것과 같은 효과가 나타난다. 

주변 원소의 근처 지뢰 갯수도 0이면, 그 주변 원소도 연쇄적으로 지뢰 갯수를 표시해준다.

3. 2차원 배열의 맨 마지막 원소에 도달할 때까지 이 작업을 반복한다.

두번째 순회에서는, 주변에 9면이 지뢰가 없는 경우가 없었기 때문에 연쇄적으로 깨지지 않고 남아있는 원소들을 찾아 깨주는 작업이다. 

주변에 몇개의 지뢰가 남아있는지 굳이 셀 필요 없이 갯수만 세어주면 된다.

파이썬 코드

def checkAroundPos(arr, aroundPos):
    """
    체크해야할 주변 원소들을 aroundPos에 넣으면서 주변에 지뢰의 갯수를 세어준다.
    지뢰면 더이상 그 방향을 탐색하지 않는다.
    """
    dx = [1, -1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, 1, -1, -1, 1, -1, 1]
 
    while aroundPos:
        # 주변을 탐색해야 하는 pos
        x,y = aroundPos.pop(0)
        count = 0
        temp_around = []
 
        # 이미 탐색한 지점인 경우 pass
        if arr[x][y] != '.':
            continue
 
        for i in range(8):
            temp_x = x + dx[i]
            temp_y = y + dy[i]
 
            if temp_x >= 0 and temp_y >= 0 and temp_x < n and temp_y < n:
                value = arr[temp_x][temp_y]
                if value == "*":
                    count += 1
                elif value == ".":
                    temp_around.append((temp_x,temp_y))
        arr[x][y] = count
        # 주변에 지뢰가 없는 pos일 경우만 주변도 탐색
        if count == 0:
            aroundPos += temp_around
 
def solve(arr, n):
    dx = [1, -1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, 1, -1, -1, 1, -1, 1]
    click_count = 0
 
    # 첫번째 순회
    # 주변 8면에 지뢰가 없는 위치를 우선으로 탐색
    for i in range(0, n*n):
        next_pos = False
        x, y = i // n, i % n
        # 이미 탐색햇거나 지뢰의 경우 생략
        if arr[x][y] != '.':
            continue
 
        aroundPos = []
        for d in range(8):
            temp_x = x + dx[d]
            temp_y = y + dy[d]
            # 지뢰인 경우 체크
            if temp_x >= 0 and temp_y >= 0 and temp_x < n and temp_y < n:
                # 지뢰일 경우 다음으로 넘긴다
                if arr[temp_x][temp_y] == '*':
                    next_pos = True
                    break
                else:
                    aroundPos.append((temp_x, temp_y))
        if next_pos:
            continue
 
        # 모든 면이 지뢰가 아닐 경우에 클릭
        click_count += 1
        arr[x][y] = 0
        # 주변 탐색
        checkAroundPos(arr, aroundPos)
 
    # 두번째 순회
    # 주변이 지뢰가 하나라도 남아있고, 연쇄적으로 터지지 않은 경우 탐색
    for i in range(0, n*n):
        x, y = i // n, i % n
        if arr[x][y] == '.':
            click_count += 1
 
    return click_count
 
 
if __name__ == "__main__":
    t = int(input())
    for i in range(t):
        n = int(input())
        arr = []
        for j in range(n):
            arr.append(list(input().strip()))
        print('#{0} {1}'.format(t+1, solve(arr, n)))
 

#1868 파핑파핑 지뢰찾기 #python 1868 파핑파핑 지뢰찾기 #1868 파핑파핑 지뢰찾기 python #sw expert 1868 파핑파핑 지뢰찾기 #sw expert 1868 #파이썬 1868 파핑파핑 지뢰찾기 #1868 파핑파핑 지뢰찾기 파이썬