코딩테스트 역량 강화 교육(거점형 특화 프로그램)이라는 프로그램에 참여해 공부한 내용입니다.

• IT 직무로 취업을 희망하는 지원자들이 코딩테스트를 통과할 수 있는 알고리즘을 활용한 프로그래밍 교육이며, PCCP 자격증 취득이 목표인 프로그램
• 상세 설명 - 수원대학교(대학일자리 플러스센터)

---

DFS - 검정색 영역 구하기

앞서 공부한 DFS(깊이 우선 탐색)을 사용해 검정색 영역 구하기 문제를 풀어보겠다.

---

문제

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

상하좌우로 1(검정색)이 연결되어 있으면 한 영역으로 간주합니다.
화면의 격자 정보가 위와 같다면 검정색으로 칠해진 영역은 2곳입니다.
매개변수 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]]	2
[[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]]	5
[[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]]	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]]	5

---

제한사항

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

---

코드

dr = [-1, 0, 1, 0]
dc = [0, 1, 0, -1]

def DFS(n, m, r, c, board):
    board[r][c] = 0
    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(n, m, nr, nc, board)

def solution(board):
    answer = 0
    n = len(board)
    m = len(board[0])

    for i in range(n):
        for j in range(m):
            if board[i][j] == 1:
                answer += 1
                DFS(n, m, 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]]))

---

풀이

• 일단 board의 모든 원소를 돌면서 검정색 영역인지 확인한다.
• 검정색 영역이라면 DFS에 board의 크기 n, m과 현재 좌표와 board를 담아 호출한다.
• DFS는 호출되면 우선 현재 좌표는 검은색 영역이므로 흰색으로 변경해놓는다.
• 그 후, 해당 좌표에 상하좌우 네 방향을 방향 배열 dr, dc를 이용해 모니터를 벗어나지 않으면서 검은색 영역인지 확인한다.
• 만약 검은색 영역이라면 이동한 좌표인 nr, nc좌표를 기준으로 DFS를 호출한다.
• 모든 검은색 영역을 다 이동하면 전부 흰색 영역(0)으로 변경되어 있으며, 해당 검은 영역을 다 탐색한 것이므로 영역 수(answer)를 +1 한다.
• 그렇게 모든 board의 모든 원소를 돌아 흰색 영역으로 변경한 뒤 카운팅해 return answer한다.