[Python] 프로그래머스 - 안전지대

0단계 문제를 푸는데 꽤 어려운 문제가 나왔다!

https://school.programmers.co.kr/learn/courses/30/lessons/120866

프로그래머스

 

# 내 풀이

def solution(board):
    answer = 0
    dx = [-1, 1, 0 , 0, 1, 1, -1, -1]
    dy = [0, 0, -1, 1, -1, 1, 1, -1]
    for i in range(len(board)):
        for j in range(len(board)):
            if board[i][j]==1:
                for k in range(8):
                    nx = i+dx[k]
                    ny = j+dy[k]
                    if 0<=nx<len(board) and 0<=ny<len(board):
                        if board[nx][ny]!=1:
                            board[nx][ny] = -1
    for i in board:
        for j in i:
            if j==-1 or j==1:
                answer +=1
    return len(board)*len(board)-answer

• 내가 푼 방식. dx, dy 리스트 선언 후 이동할 때마다 현재 위치가 1이라면, 상하좌우대각선의 8개 위치를 돈다.
• 이때 바로 이동하면 인덱스 에러가 날 수 있으므로 nx,ny로 미리 보드의 범위를 벗어나지 않는지 체크한 후 이동한다.
• 또한 상하좌우대각선 위치에 지뢰가 있는지(1인지) 검사해야 한다. 지뢰가 있는데 위험지역으로 표시하면 안되므로...나는 위험지역은 -1로 표시했다.

 

 

# 프로그래머스 풀이

def solution(board):
    n = len(board)
    danger = set()
    for i, row in enumerate(board):
        for j, x in enumerate(row):
            if not x:
                continue
            danger.update((i+di, j+dj) for di in [-1,0,1] for dj in [-1, 0, 1])
    return n*n - sum(0 <= i < n and 0 <= j < n for i, j in danger)

• 가장 좋아요를 많이 받은 풀이. 나도 이제 enumerate를 쓸 줄 알아야지...
• enumerate란 일단 반복문이다. 특히 순회가 가능한 리스트, 문자열, 반복자 등등..에서 for문 대신 쓰면 좋다. enumerate()를 사용하게 되면 튜플의 형태로 (인덱스, 원소)를 반환한다! 
• 이 코드에서는 지뢰가 1이라는 것을 이용해 코드도 간단하게 작성했다.
• 만약 1이 아니라면, danger라는 집합에 위험지대의 위치+지뢰의 위치를 튜플로 저장했다. set()은 중복 저장이 아니니..좋은 생각..! 또 저장할 때 for문을 이용해 간단하게 작성했다.

>>> for i, letter in enumerate(['A', 'B', 'C'], start=1):
...     print(i, letter)
...
1 A
2 B
3 C

• enumerate()의 예시. start 인자를 이용해 인덱스의 시작을 조절할 수도 있다.

 

# DFS

from collections import deque

def solution(board):
    dx = [-1, 1, 0 , 0, 1, 1, -1, -1]
    dy = [0, 0, -1, 1, -1, 1, 1, -1]
    length = len(board)
    visited = [[False] * length for _ in range(length)]

    def bfs(x, y):
        dq = deque()
        dq.append((x, y))
        while dq:
            a, b = dq.popleft()
            visited[a][b] = True
            for i in range(8):
                nx = dx[i] + a
                ny = dy[i] + b
                #위험지역으로 둬야함 
                if 0<=nx<length and 0<=ny<length and not visited[nx][ny]:
                    if board[nx][ny] == 1:
                        dq.append((nx, ny))
                    else:
                        board[nx][ny] = 2 #위험지역 처리 

    for i in range(length):
        for j in range(length):
            if board[i][j] == 1:
                bfs(i, j)
    result = 0
    for i in range(length):
        result += board[i].count(0)
    return result

• 마침 지금 탐색을 배우고 있는 김에...BFS 풀이가 있길래 가져왔다.
• visited 리스트를 활용해 탐색 기록 저장!
• BFS는 board가 1인 경우에 돈다. 만약 지뢰 주변지역에 지뢰가 또 있다면 queue()에 저장한다. 지뢰가 없으면 그냥 board에 따로 1과 0을 제외한 수 입력.
• 입력 범위도 적고...굳이 BFS까지는 아닌 문제인듯. 애초에 탐색이 0단계에서 나오면 안됨. 그래도 연습할 겸 가져왔다.