코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.
- IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
- 상세 설명 - 수원대학교(대학일자리 플러스센터)
DFS - 픽셀 수 구하기
앞서 공부한 DFS(깊이 우선 탐색)을 사용해 픽셀 수 구하기 문제를 풀어보겠다.
문제
5 * 5 이차원 배열에 모니터 화면을 표현합니다. 모니터의 화면은 최초 검정색과 흰색으로만 표현되어 있습니다. 검정색은 1, 흰색은 0으로 표현됩니다.
상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다.
화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2이고, 첫 번째 영역의 픽셀수(격자 수)는 5개이고, 두 번째 영역의 픽셀수는 3개입니다.
매개변수 board에 모니터 화면의 격자정보가 주어지면 검정색으로 칠해진 각 영역의 픽셀수를 순서대로 배열에 담아 반환하세요.
영역의 순서는 각 영역의 행번호, 열번호가 가장 작은 픽셀을 기준으로 행번호가 작은 것부터이며 행번호가 같을 경우 열 번호가 작은 영역 순으로 배열에 담습니다.
입출력 예
| board | answer |
|---|---|
| [[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]] | [5, 3] |
| [[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]] | [7, 2, 3, 1, 1] |
| [[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]] | [4, 1, 3] |
| [[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]] | [1, 1, 1, 2, 1] |
제한사항
- 검정색 영역은 1개 이상 반드시 존재합니다.
코드
dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]
count = 0
def DFS(r, c, n, m, board):
global count
board[r][c] = 0
count += 1
for i in range(4):
nr = r + dr[i]
nc = c + dc[i]
if nr >= 0 and nr < n and nc >= 0 and nc < m and board[nr][nc] == 1:
DFS(nr, nc, n, m, board)
def solution(board):
global count
answer = []
n = len(board)
m = len(board[0])
for i in range(n):
for j in range(m):
if board[i][j] == 1:
count = 0
DFS(i, j, n, m, board)
answer.append(count)
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]]))
풀이
이 문제는 DFS - 검정색 영역 구하기 문제와 매우 흡사하다.
- 일단
board의 모든 원소를 돌면서 검정색 영역인지 확인한다. - 검정색 영역이라면 해당 검정색 영역의 개수를 세기 위해
count를0으로 초기화시키고,DFS에 board의 크기 n, m과 현재 좌표와 board를 담아 호출한다. DFS는 호출되면 우선 현재 좌표는 검은색 영역이므로 흰색으로 변경해놓고,개수(count)를 하나 센다.- 그 후, 해당 좌표에 상하좌우 네 방향을 방향 배열
dr,dc를 이용해 모니터를 벗어나지 않으면서 검은색 영역인지 확인한다. - 만약
검은색 영역이라면 이동한 좌표인nr,nc좌표를 기준으로 DFS를 호출한다. - 모든 검은색 영역을 다 이동하면 전부 흰색 영역(0)으로 변경되어 있으며, 해당 검은 영역을 다 탐색한 것이므로
검정색 영역 수(count)를answer에 삽입한다. - 그렇게 모든
board의 모든 원소를 돌아 흰색 영역으로 변경한 뒤 각각의 검정색 영역의 횟수를 세 삽입한answer를return
끄적끄적