[백준/Python] #10026 적록색약

문제

 

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

10026번: 적록색약

---

Algorithm

2차원 배열 array를 입력받을 때 array의 각 위치를 지나쳤는지에 대한 배열 V를 함께 생성한다. V의 모든 원소는 False로 초기화한다. 같은 방법으로 v를 생성하는데 v는 색약이 아닌 사람, V는 색약인 사람에 대한 배열이다.

모든 과정은 색약인 사람은 "R"과 "G"인 부분을 "A"로 치환하여 진행한다. array의 행과 열 (i, j)에 대해 array[i][j]가 처음 마주하는 영역이면 함수 visited를 실행한다. array[i][j]가 visited를 통해 마주한 적이 있는 영역이면 건너뛰어 진행한다.

함수 visited는 array의 상하좌우를 탐색하여 현재 위치의 값과 같은 영역인 부분으로 이동해 V 또는 v를 True로 바꾼다. 색약인 사람인 경우에는 "R"이나 "G"일 때가 적어도 하나 있다면 그 방향에 해당하는 값을 "A"로 바꾸고 탐색한다. 

이렇게 진행하면서 visited가 실행된 횟수를 출력한다.

 

---

 

 

Code

from sys import stdin
from collections import deque
import sys
sys.setrecursionlimit(3000000)

input = stdin.readline

n = int(input())
array = deque()

v = deque()
V = deque()
for _ in range(n):
    array.append(list(input()[: -1]))
    v.append(deque([False] * n))
    V.append(deque([False] * n))
    
def search(center):
    a, b = center
    if b > 0:
        left = array[a][b - 1]
    else:
        left = "None"
    if b < n - 1:
        right = array[a][b + 1]
    else:
        right = "None"
    if a > 0:
        up = array[a - 1][b]
    else:
        up = "None"
    if a < n - 1:
        down = array[a + 1][b]
    else:
        down = "None"
    return (left, (a, b - 1)), (right, (a, b + 1)), (up, (a - 1, b)), (down, (a + 1, b))


def visited(i, target):
    connected = False

    (left, l), (right, r), (up, u), (down, d) = search(i)
    if target == "A":
        if left == "R" or left == "G":
            left = "A"
            
        if right == "R" or right == "G":
            right = "A"
        
        if up == "R" or up == "G":
            up = "A"
        
        if down == "R" or down == "G":
            down = "A"
            
    if left == target:
        if V[l[0]][l[1]] == False:
            connected = True
            V[l[0]][l[1]] = True
            visited(l, target)
    
    if right == target:
        if V[r[0]][r[1]] == False:
            connected = True
            V[r[0]][r[1]] = True
            visited(r, target)
    
    if up == target:
        if V[u[0]][u[1]] == False:
            connected = True
            V[u[0]][u[1]] = True
            visited(u, target)
            
    if down == target:
        if V[d[0]][d[1]] == False:
            connected = True
            V[d[0]][d[1]] = True
            visited(d, target)
    
    if connected == False:
        return

b = 0
a = 0
for i in range(n):
    for j in range(n):
        rgb = array[i][j]
        nb = array[i][j]
        if nb == "R":
            nb = "A"
        elif nb == "G":
            nb = "A"
        if v[i][j] == False:
            temp = V.copy()
            V = v.copy()
            visited((i, j), rgb)
            V = temp.copy()
            a += 1
        if V[i][j] == False:
            visited((i, j), nb)
            b += 1
    
print(a, b)