[백준(BOJ)] #10026- 적록색약 (파이썬, Python3)

문제

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

---

문제 풀이

DFS 알고리즘 적용!

 

2022.07.12 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

 

적록색약인 사람은 빨간색과 초록색의 차이를 거의 못 느끼기 때문에 일반 사람들이 보는 그리드 A에서 초록색을 모두 빨간색으로 바꿔 구역의 수를 구해주면 됩니다.

 

1) 일반 사람들이 보는 그리드 a를 입력 받는다.
2) 그리드 a에서 초록색을 모두 빨간색으로 바꾼 그리드 b를 만든다.
3) 각각 그리드에서 방문 여부를 체크하는 visited 리스트를 생성한다.
4) DFS 알고리즘을 적용하여 구역의 수를 구한다.

 

---

구현

코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

def dfs(board, visited, pos, color):
    tx, ty = pos
    board[tx][ty] = '-'
    visited[tx][ty] = True
    for k in range(4):
        x = tx + dx[k]
        y = ty + dy[k]
        if 0 <= x < N and 0 <= y < N and board[x][y] == color and not visited[x][y]:
            dfs(board, visited, (x, y), color)

if __name__ == "__main__":
    colors = ['R', 'G', 'B']
    N = int(input())
    a = list(list(map(str, input().rstrip())) for _ in range(N))
    b = [[''] * N for _ in range(N)]
    # 적록색약이 보는 그리드를 구해주는 작업
    for i in range(N):
        for j in range(N):
            if a[i][j] == 'R' or a[i][j] == 'G':
                b[i][j] = 'R'
            else:
                b[i][j] = 'B'
    visited_a = [[False] * N for _ in range(N)]
    visited_b = [[False] * N for _ in range(N)]
    res_a = 0
    res_b = 0

    for i in range(N):
        for j in range(N):
            if a[i][j] in colors:
                res_a += 1
                if a[i][j] == 'R':
                    dfs(a, visited_a, (i, j), 'R')
                elif a[i][j] == 'G':
                    dfs(a, visited_a, (i, j), 'G')
                elif a[i][j] == 'B':
                    dfs(a, visited_a, (i, j), 'B')
            if b[i][j] in colors:
                res_b += 1
                if b[i][j] == 'R':
                    dfs(b, visited_b, (i, j), 'R')
                elif b[i][j] == 'B':
                    dfs(b, visited_b, (i, j), 'B')
    print(res_a, res_b)

결과