[python] 프로그래머스 안전지대(방향탐색)

# 120866 안전지대
https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

⭐ 코드

def solution(board):
    N = len(board)
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
    
    # 지뢰 설치
    boom = []
    for i in range(len(board)):
        for j in range(len(board)):
            if board[i][j] == 1:
                boom.append((i,j)) # 지뢰일때의 인덱스 append
                    
    # 지뢰가 설치된 곳 주변에 폭탄 설치
    for x, y in boom:
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                board[nx][ny] = 1

    # 폭탄이 설치되지 않은 곳만 카운팅
    count = 0
    for x in range(N):
        for y in range(N):
            if board[x][y] == 0:
                count += 1
    return count

📝 풀이

지뢰찾기 게임을 해봤기 때문에 문제를 이해하는데 시간이 오래걸리진 않았다. 처음에는 단순하게 4방향 탐색으로 지뢰 주변을 카운트해주고, 총 갯수에서 빼주면 되겠다 라고 생각했었는데 그렇게 하게되면 중복일때와 지뢰 대각선 부분을 카운트하기 어려웠다.

 

이 문제의 핵심은

1. 지뢰(1)일때의 인덱스를 기록하고

2. 지뢰가 설치된 주변에 지뢰를 심어주고

3. 지뢰가 설치되지 않은 곳들을 카운팅 한다

 

또한 4방향 탐색을 하면 지뢰 대각선을 카운팅 할 수 없으므로 8방향 탐색을 진행시켜준다.

🔓 코드 뜯어보기

def solution(board):
    N = len(board)
    dx = [-1, 1, 0, 0, -1, -1, 1, 1]
    dy = [0, 0, -1, 1, -1, 1, -1, 1]
    
    # 지뢰 설치
    boom = []
    for i in range(len(board)):
        for j in range(len(board)):
            if board[i][j] == 1:
                boom.append((i,j)) # 지뢰일때의 인덱스 append

나중에 방향탐색을 할 때 경계값을 걸어주기 위해서 N에 리스트의 길이를 저장시켜준다.

8방향 탐색을 위한 dx, dy를 만들어주고, 지뢰의 인덱스를 담기 위해 for문을 통해서 지뢰위치를 기록해준다.

 # 지뢰가 설치된 곳 주변에 폭탄 설치
    for x, y in boom:
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                board[nx][ny] = 1

    # 폭탄이 설치되지 않은 곳만 카운팅
    count = 0
    for x in range(N):
        for y in range(N):
            if board[x][y] == 0:
                count += 1
    return count

그 다음 저장된 인덱스를 꺼내주면서 지뢰 위치로부터 8방향 탐색을 시켜주고, 범위 내에 있는 위치들을 1로 바꿔준다.

그 후 안전한 지역을 카운트하기 위한 count를 만들어주고, 이중반복문을 통해 0인 곳들을 탐색할때마다 count에 1씩 더해주고 return값에 count를 출력해준다.