코딩테스트입문 / 안전지대 (방향탐색,BFS)

📚문제

출처 : 프로그래머스 / 안전지대(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]

    # 지뢰의 위치(인덱스)
    mine = []
    for i in range(n):
        for j in range(n):
            if board[i][j] == 1: # 지뢰일때의 인덱스
                mine.append((i,j))
                    
    # 지뢰가 설치된 곳 주변에 폭탄 설치
    for x, y in mine:
        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

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

 

정말 어렵군요...LV0 입문이 맞나요..?

아직 갈 길이 멀다는 생각이 들면서도 

배울 게 많아서 행복하네요 ㅎㅎㅎㅎㅎ

 

보자마자 직감적으로 내 실력으로는 아직 무리인 것 같아서 

구글링하여 코드 참고 & 분석 

 

 

1. 지뢰 위치 (인덱스) 설정

n = len(board)
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]

# 지뢰의 위치(인덱스)
mine = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 1: # 지뢰일때의 인덱스
            mine.append((i,j))

 

1) board의 길이(len) 설정 => 방향탐색 시 경계값을 만들기 위해

2) 8방향 탐색(상,하,좌,우,대각선)을 위한 dx,dy 생성 =>

이 부분은 잘 이해가 안된다 방향탐색 개념시에 같이 등장하는 것 같은데 어떤 공식 같은건가?

후술하는 지뢰 주변에 폭탄 설치하는 코드 부분을 보다 보니 이해가 되었다

어떤 좌표가 주어지면 그 좌표 주변으로

행렬상에서 움직이듯이 생각하면된다

흠..그림실력 실화 ?

아무튼 dx, dy가 어떻게 나오게 됐으며 다음에도 어떤식으로 지정해주어야하는지 이해가 되었다.

 

2. 지뢰 주변에 폭탄 설치

 board = [[0, 0, 0, 0, 0], 
	[0, 0, 0, 0, 0], 
        [0, 0, 0, 0, 0], 
        [0, 0, 1, 1, 0], 
        [0, 0, 0, 0, 0]]
인 경우를 예로 들어보면 

mine = [(3, 2), (3, 3)] 
dx = [-1, 1, 0, 0, -1, -1, 1, 1]
dy = [0, 0, -1, 1, -1, 1, -1, 1]
---------------------------------------------
 
 # 지뢰가 설치된 곳 주변에 폭탄 설치
    for x, y in mine: # 1번째 (3,2) /  2번째 (3,3) 
        for i in range(8): # 8방향 탐색 진행
            nx = x + dx[i] # (3-1,3+1,3+0,3+0,3-1,3-1,3+1,3+1) / (3-1,3+1,3+0,3+0,3-1,3-1,3+1,3+1)
            ny = y + dy[i] # (2+0,2+0,2-1,2+1,2-1,2+1,2-1,2+1) / (3+0,3+0,3-1,3+1,3-1,3+1,3-1,3+1)
            if 0 <= nx < n and 0 <= ny < n: # 0일경우는 상관없지만 board 길이보다 큰 경우는 제외
                board[nx][ny] = 1 # 지뢰 주변으로 폭탄 설치

 

3. 폭탄과 지뢰설치되지 않은 안전지대(=0) 카운트

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

 

 

 

+ 방향탐색 BFS(너비우선탐색) 이라는 알고리즘의 한 방법으로도 풀이한 것 기록

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

deque를 import한 것을 보니 스택(Stack/후입선출) 과 큐(Queue/선입선출) 의 개념이다.

기존에 그냥 8방향 탐색방법으로 푼 것과 거~의 유사해 보이는데 ... 조금 차이는 있는 것 같다

나중에 알고리즘 방법 공부 하고나면 그 때 다시 코드를 살펴봐야겠다