[DFS] -픽셀수 구하기

 

픽셀수 구하기

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

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

 

상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다.
화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2이고, 첫 번째 영역의 픽셀수(격 자수)는 5개이고, 두 번째 영역의 픽셀수는 3개입니다.
매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 각 영역의 픽셀수를 순서대로 배열에 담아 반환하세요. 영역의 순서는 각 영역의 행번호, 열번호가 가장 작은 픽셀 을 기준으로 행번호가 작은 것부터이며 행번호가 같을 경우 열 번호가 작은 영역 순으로 배열 에 담습니다.

 

 

나의 코드

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

def DFS(x,y,board):
    global cnt
    cnt+=1
    board[x][y]=0
    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)

cnt=0
def solution(board):
    answer = []
    global cnt

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

이전 문제와 거의 비슷한 문제지만 영역을 카운팅 하는것과 다르게 한 영역에 몇개의 요소가 있는지 확인을 해야한다.

cnt를 어디 부분에서 카운팅 해야하는지에 대한 고민을 했고 cnt를 어디에 선언을 해야하는지도 꽤나 고민을 했다.

 

 

즉, 2중 for문 내에서 처음 DFS가 호출 된 이후  DFS함수 내부적으로 재귀적으로 탐색하여 1을 만날 때 마다 카운팅을 하면 한영역 내에서의 1의 갯수를 카운팅할 수 있다.

 

++) 영역의 수는 이중 포문 내에서 DFS가 처음 호출되는 횟수이다.!

 

 

 

 

정답 코드

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

오오 큐큐 거의 똑같다 ㅋㅋ 야미