[Python] Baekjoon - 10026. 적록색약

빨간색과 초록색의 차이를 거의 느끼지 못하는 것을 적록색약이라고 한다. 백준 10026번 적록색약 문제는 RGB로 구성된 그림에 대해 적록색약인 사람과 아닌 사람이 봤을 때 보이는 구역의 수를 구하는 문제이다. 그래프 탐색 알고리즘을 이용하여 해결할 수 있으며 난이도는 골드 5이다.

 

백준 10026번 적록색약 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- 골드 5

 

적록색약 문제 요약

NxN 크기의 그리드의 각 칸이 R, G, B 중 하나의 색으로 칠해져 있다. 하나의 색으로 이어진 칸들을 하나의 구역이라고 하는데, 적록색약인 사람은 R과 G가 거의 구분이 가지 않아 하나의 색으로 보인다고 한다. 적록색약이 아닌 사람에게 보이는 구역의 개수와, 적록색약인 사람에게 보이는 구역의 개수 구하여라.

 

문제 풀이 과정

적록색약이 아닌 사람과 적록색약인 사람, 두가지 경우에 같은 함수를 재사용하기 위해 적록색약인 사람의 구역 수를 구하는 과정에서 초록색을 빨간색으로 모두 변경한다.

아직 방문하지 않은 칸에 대해서 인접한 같은 색 칸을 모두 방문하는 함수 사용한다.

 

자세한 풀이

• get_areas(tc): 방문한적 없는 새로운 칸들을 방문하며 구역 수를 구하는 함수이다.
  • tc는 visited배열을 초기화하지 않기 위해 사용한다.
• visited_area(start, color, tc): start칸을 기준으로 인접한 같은 색인 칸들을 방문하는 함수이다.
  • 인접한 칸들을 모두 방문하기 위해 DFS 사용한다.
  • 각 칸을 방문하는 과정에서 초록색인 칸을 빨간색으로 변경한다.

 

코드

# start 좌표를 기준으로 같은 색인 칸들을 방문하는 함수
def visit_area(start, color, tc):
    global N, board, visited
    dr, dc = [1,-1,0,0], [0,0,1,-1]
    r, c = start

    stack = [(r, c)]

    while stack:
        here_r, here_c = stack.pop()

        if visited[here_r][here_c] == tc:
            continue

        visited[here_r][here_c] = tc

        # 두번째 tc(적록색약)에서 색 구분을 없애기 위해 G를 모두 R로 변경
        if color == 'G':
            board[here_r][here_c] = 'R'

        # 아직 방문한적 없고 색이 같으면 스택에 넣기
        for d in range(4):
            next_r, next_c = here_r + dr[d], here_c + dc[d]
            if 0 <= next_r < N and 0 <= next_c < N and visited[next_r][next_c] != tc and board[next_r][next_c] == color:
                stack.append((next_r, next_c))


# 방문한적 없는 새로운 칸들을 방문하며 구역 수를 구하는 함수
def get_areas(tc):
    global N, board

    res = 0
    for r in range(N):
        for c in range(N):
            # 방문한적 없는 칸 방문하고 구역 수 증가 시키기
            if visited[r][c] != tc:
                res += 1
                visit_area((r, c), board[r][c], tc)

    return res


if __name__ == '__main__':
    N = int(input())
    board = []
    visited = [[0 for _ in range(N)] for _ in range(N)]

    for _ in range(N):
        tmp = input().strip()
        board.append([*tmp])

    print(get_areas(1), end=' ')
    print(get_areas(2))