BOJ 10026(python) : 적록색약

문제링크

예제 입력 1
5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1
4 3

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
적록색약 : G,R을 구별 못 함

---

Solution

Base:
깊이 우선 탐색을 사용하여 R,G,B 일 때를 모두 탐색

def bfs(x,y,color):
    global isvisited
    isvisited[x][y] = True
    dx = [0,1,0,-1] #위 아래 왼쪽 오른쪽 방향 설정
    dy = [1,0,-1,0]
    for i in range(4):
        mx = dx[i] + x
        my = dy[i] + y
        if 0 <= mx <n and 0 <= my < n:
            if isvisited[mx][my] == False and arr[mx][my] == color:
                bfs(mx,my,color)

isvisited를 global로 사용하여 이미 방문한 곳은 패스

for i in range(n):
    for j in range(n):
        if isvisited[i][j] == False:
            bfs(i,j,arr[i][j])
            cnt+=1

Develop

BFS를 돌면서 R 또는 G 이거나 B 일 때로 조건문을 변경

def bfs_rg(x,y,color):
   global isvisited
   isvisited[x][y] = True
   dx = [0,1,0,-1]
   dy = [1,0,-1,0]
   for i in range(4):
       mx = dx[i] + x
       my = dy[i] + y
       if 0 <= mx <n and 0 <= my < n:
           if isvisited[mx][my] == False:
               if color == 'R' or color == 'G':
                   if arr[mx][my] == 'R' or arr[mx][my] == 'G':
                       bfs_rg(mx,my,color)
               else:
                   if arr[mx][my] == 'B':
                       bfs_rg(mx,my,color)

---

전체소스

import sys

sys.setrecursionlimit(10**9)

n = int(sys.stdin.readline())
arr = list()
isvisited= [[False] * n for _ in range(n)]
for i in range(n):
    arr.append(sys.stdin.readline().strip())
cnt = 0

#색약이 아닌 사람
def bfs(x,y,color):
    global isvisited
    isvisited[x][y] = True
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
        mx = dx[i] + x
        my = dy[i] + y
        if 0 <= mx <n and 0 <= my < n:
            if isvisited[mx][my] == False and arr[mx][my] == color:
                bfs(mx,my,color)

#R,G을 구별 못하는 사람
def bfs_rg(x,y,color):
    global isvisited
    isvisited[x][y] = True
    dx = [0,1,0,-1]
    dy = [1,0,-1,0]
    for i in range(4):
        mx = dx[i] + x
        my = dy[i] + y
        if 0 <= mx <n and 0 <= my < n:
            if isvisited[mx][my] == False:
                if color == 'R' or color == 'G':
                    if arr[mx][my] == 'R' or arr[mx][my] == 'G':
                        bfs_rg(mx,my,color)
                else:
                    if arr[mx][my] == 'B':
                        bfs_rg(mx,my,color)

for i in range(n):
    for j in range(n):
        if isvisited[i][j] == False:
            bfs(i,j,arr[i][j])
            cnt+=1
print(cnt,end=" ")
isvisited= [[False] * n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if isvisited[i][j] == False:
            bfs_rg(i,j,arr[i][j])
            cnt+=1
print(cnt)