[DFS] -검정색 구하기

검정색 영역구하기

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

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

 

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

 

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

 

나의 코드

def DFS(x,y,board):
    board[x][y]=0
    dx=[-1,0,1,0]
    dy=[0,1,0,-1]
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if 0<=nx<len(board) and 0<= ny <len(board) and board[nx][ny]==1:
            DFS(nx,ny,board)


def solution(board):
    answer = 0
    for i in range(len(board)):
        for j in range(len(board)):
            if board[i][j]==1:
                DFS(i,j,board)
                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]]))

 

방향 벡터를 사요하여 주어진 board를 DFS탐색을 한다.

DFS탐색을 하며 board배열 자체를 체크 배열로 사용하여 1을 만났을 때 0 으로 바꿔주어 탐색 했음을 체크 한다.

 

+ 이중 포문 내에서 1을 처음 만나 DFS함수를 호출 하는 횟수가 바로 영역의 횟수이다.

왜냐하면 DFS함수내에서 주변 동서남북 방향으로 1을 만날 때 마다 0으로 변경해준뒤 그 영역이 모두 0 으로 바꾸면 처음 이중 포문에서 호출한 함수의 실행이 종료 되기 때문이다.

 

 

즉 DFS를 한번 탐색하면 한 영역이 모두 0으로 바뀌며 한 영역의 탐색이 끝난다.

 

 

 

정답 코드

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def DFS(x, y, board):
    board[x][y] = 0
    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:
            DFS(nx, ny, board)
         
def solution(board):
    answer = 0
    for i in range(5):
        for j in range(5):
            if board[i][j] == 1:
                answer += 1
                DFS(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]]))

나의 코드와 똑같다.