적록색약

출처 : 백준 #10026

시간 제한	메모리 제한
1초	128 MB

---

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

---

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

---

출력

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

---

입출력 예시

예제 입력 1

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1

4 3

---

풀이

풀이 설명

• BFS : python 자료구조인 Deque을 이용하였다.
• 적록색약이 아닐 때(함수 bfs)와 적록색약일 때(함수 rgb)를 구분하여 사용하였다.
• 메모리 공간을 아끼기 위해 visited를 처음엔 False로, 두번째엔 True로 놓고 계산하였다.
• 함수 bfs를 먼저 계산할 때 'G'를 모두 'R'로 바꿔 놓고, 함수 rgb를 쓸 때 이용하였다.

python code(DFS)

# 백준 10026번
from sys import stdin
from collections import deque

def solution(n, matrix, visited):
    queue = deque()
    count = 0
    rgb_count = 0

    for i in range(n):
        for j in range(n):
            if visited[i][j] == False:
                queue.append((i, j))
                visited[i][j] = True
                bfs(queue, matrix, visited)
                count += 1
    
    for i in range(n):
        for j in range(n):
            if visited[i][j] == True:
                queue.append((i, j))
                rgb(queue, matrix, visited)
                rgb_count += 1
    
    print(count, end=" ")
    return rgb_count




def bfs(queue, matrix, visited):
    dx = [0, -1, 0, +1]
    dy = [+1, 0, -1, 0]
    while queue:
        col, row = queue.popleft()
        cur = matrix[col][row]
        if cur == 'G':
            matrix[col][row] = 'R'
        for i in range(4):
            temp_col = col+dx[i]
            temp_row = row+dy[i]
            if 0 <= temp_col < n and 0 <= temp_row < n:
                if matrix[temp_col][temp_row] == cur and visited[temp_col][temp_row] == False:
                    visited[temp_col][temp_row] = True
                    queue.append((temp_col, temp_row))
    return 

def rgb(queue, matrix, visited):
    dx = [0, -1, 0, +1]
    dy = [+1, 0, -1, 0]
    while queue:
        col, row = queue.popleft()
        cur = matrix[col][row]
        for i in range(4):
            temp_col = col+dx[i]
            temp_row = row+dy[i]
            if 0 <= temp_col < n and 0 <= temp_row < n:
                if matrix[temp_col][temp_row] == cur and visited[temp_col][temp_row] == True:
                    visited[temp_col][temp_row] = False
                    queue.append((temp_col, temp_row))
    return 







n = int(stdin.readline())
matrix = []
visited = []
for i in range(n):
    matrix.append(list(stdin.readline()))
    visited.append([False for _ in range(n)])

print(solution(n, matrix, visited))