[백준`G5] 10026 - 적록색약 (Python)

문제 설명

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

10026번: 적록색약

---

문제 풀이

구역의 개수를 구하는 문제이기 때문에 DFS로 풀었다! 

파이썬은 재귀 limit이 있어서 setrecursionlimit으로 최대 재귀 횟수를 설정해주어야 한다.

RGB배열을 만들어 하나씩 꺼내가며 R, G, B구역의 개수 더해가면서 적록색약이 아닌 사람이 봤을 때 구역을 구하였고,

G를 R로 바꾸어 적록색약인 사람이 보는 구역의 수를 구했다.

 

 

import sys

sys.setrecursionlimit(100000)


def dfs(x, y, color):
    if x < 0 or x >= n or y < 0 or y >= n:
        return False
    if not visited[x][y] and area[x][y] == color:
        visited[x][y] = True
        for k in range(4):
            nx = x + dx[k]
            ny = y + dy[k]
            dfs(nx, ny, color)
        return True
    return False


n = int(input())
area = [list(input()) for _ in range(n)]
RGB, RB = ['R', 'G', 'B'], ['R', 'B']
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
rst1, rst2 = 0, 0

for c in RGB:
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if dfs(i, j, c):
                rst1 += 1

for i in range(n):
    for j in range(n):
        if area[i][j] == 'G':
            area[i][j] = 'R'

for c in RB:
    visited = [[False] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if dfs(i, j, c):
                rst2 += 1

print(rst1, rst2)