[BFS] -검정색 영역구하기

검정색 영역구하기

5 * 5 이차원 배열에 모니터 화면을 표현합니다. 모니터의 화변은 최초 검정색과 흰색으로만 표현되어 있습니다.

검정색은 1, 흰색은 0으로 표현됩니다.

 

상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다.
화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2곳입니다.
매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 영역은 총 몇 개가 있는지 구하여 반환하는 프로그램을 작성하세요.

 

제한사항:
• 검정색 영역은 1개 이상 반드시 존재합니다.

 

 

나의 코드

from collections import deque
def solution(board):
    answer = 0

    dx=[-1,0,1,0]
    dy=[0,1,0,-1]

    dq=deque()


    for i in range(5):
        for j in range(5):
            if board[i][j]==1:               
                dq.append([i,j])
                while dq:
                    n=len(dq)
                    for _ in range(n):
                        x,y=dq.popleft()
                        for k in range(4):
                            nx=x+dx[k]
                            ny=y+dy[k]
                            if 0<=nx<5 and 0<=ny<5 and board[nx][ny]==1:
                                dq.append([nx,ny])
                                board[nx][ny]=0
                answer+=1

    return answer
            
print(solution([[0, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 1, 0]]))
print(solution([[1, 1, 1, 0, 1], [1, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 1, 0, 1, 0], [1, 0, 1, 0, 0]]))
print(solution([[0, 0, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [1, 0, 0, 1, 0], [0, 0, 1, 1, 0]]))
print(solution([[0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 0, 1, 0, 0]]))

후 코드 잘 짠것 같다.

이제 슬슬 BFS의 전형적인 틀..? 같은게 좀 손에 익은 것 같다.

초기 탐색한 값을 deque에 넣고  while dq:를 시작하고 덱의 길이 만큼(L 깊이) 순회 하며

동서남북 4방향으로 각각 순회하며 조건에 부합하면 바로 덱에 넣는다..!

 

처음 체크 배열을 만들어서 코드를 작성하던 도중 board 자체로 체크 배열의 역활을 할 수 있어 폐기하였다.

 

 

 

정답 코드

from collections import deque
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def BFS(x, y, board):
    Q = deque()
    Q.append([x, y])
    board[x][y] = 0
    L = 0
    while Q:
        n = len(Q)
        for i in range(n):
            x, y = Q.popleft()
            for k in range(4):
                nx = x + dx[k]
                ny = y + dy[k]
                if nx >= 0 and nx < 5 and ny >= 0 and ny < 5 and board[nx][ny] == 1:
                    Q.append([nx, ny])
                    board[nx][ny] = 0
        L += 1

def solution(board):
    answer = 0
    for i in range(5):
        for j in range(5):
            if board[i][j] == 1:
                answer += 1
                BFS(i, j, board)
    
    return answer
            
print(solution([[0, 1, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 1, 1, 0]]))
print(solution([[1, 1, 1, 0, 1], [1, 1, 1, 0, 1], [0, 0, 1, 0, 0], [1, 1, 0, 1, 0], [1, 0, 1, 0, 0]]))
print(solution([[0, 0, 1, 0, 0], [0, 1, 1, 0, 0], [0, 1, 0, 0, 0], [1, 0, 0, 1, 0], [0, 0, 1, 1, 0]]))
print(solution([[0, 0, 0, 0, 1], [0, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 0, 1, 0], [0, 0, 1, 0, 0]]))

 

와 정답이랑 그냥 완전 똑같다 크크

배운대로 사고의 흐름이 잘 흘러 가는것 같군 더욱더 체화 시켜야겠다..!