boj 10026 : 적록색약

문제 주소: https://www.acmicpc.net/problem/10026

난이도: gold 5

1.문제설명

• 정상인과, 적록색약인 사람이 있다.
• 이사람들에게 N by N grid인 각 칸에 R, G, B로 칠해진 그림을 보여준다.
• 정상인, 적록색약인 사람에게 몇개의 구역으로 보이겠는가?

2.문제해결 아이디어.

• 그래프탐색을 통해 해결할 수 있다. (본인은 DFS 사용)
• DFS를 통해 특정색과 이웃한 같은색의 좌표를 처리하자
• 한번 탐색할때마다 카운트 + 1

3.문제접근법

• graph라는 2차원 리스트에 입력 정보를 받는다.
• DFS를 한번 돌때마다 R : '0', G : '1', B : '2' 이렇게 바꿔줄꺼다
  • isalpha하기 위해 문자열 형태로 바꾸고, isalpha = True이면 처리되지 않았다는 뜻이다.
• isalpha = true이면 dfs를 돌렸고 좌표말고 prev라는 매개변수를 통해 이전에 처리한 색을 담아 전달했다.
  • 이전에 전달한 색과 같은색이면 dfs를 재귀호출했다.

4.특별히 참고할 사항

• visited라는 2차원 배열을 만들면 더 깔끔하게 할수있는데....
• 괜히 이상한 아이디어에 꽂혀서 함수도 2개를 만들었다...
• 별로 범용적이지 않은 나쁜코드 같다...
• 그래도 visited를 만들지 않아도 되서 메모리는 다른사람들에비해 적게 사용했다.
• 시간도 몇몇사람들보단 빠르지만 좀더 범용적인 코드를 짤수있도록 해야겠다.

5.코드구현

#필요한것들 import
from collections import deque
from copy import deepcopy
import sys
sys.setrecursionlimit(10000)

#입력받기
n = int(input())
graph = []
for i in range(n):
    _temp = list(input())
    graph.append(_temp)
#deepcopy로 값만 복사함, 색약 케이스를 계산할 자료
cw_graph = deepcopy(graph)
normal_cnt = 0
cw_cnt = 0

#dfs세팅
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
#dfs의 기본 개념 이용했으며 새로운 좌표가 그리드 내에 있는것 확인과 더불어 새로운 좌표의 색이 이전색과 같은지 확인

def dfs_normal(graph, x, y, prev):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == prev:
            if graph[nx][ny] == 'R':
                graph[nx][ny] = '0'
                dfs_normal(graph, nx, ny, 'R')
            elif graph[nx][ny] == 'G':
                graph[nx][ny] = '1'
                dfs_normal(graph, nx, ny, 'G')
            elif graph[nx][ny] == 'B':
                graph[nx][ny] = '2'
                dfs_normal(graph, nx, ny, 'B')

def dfs_cw(graph, x, y, prev):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if prev == 'B': #이전색이 파란색인 경우
            if 0 <= nx < n and 0 <= ny < n and graph[nx][ny] == prev:
                if graph[nx][ny] == 'R':
                    graph[nx][ny] = '0'
                    dfs_cw(cw_graph, nx, ny, 'R')
                elif graph[nx][ny] == 'G':
                    graph[nx][ny] = '1'
                    dfs_cw(cw_graph, nx, ny, 'G')
                elif graph[nx][ny] == 'B':
                    graph[nx][ny] = '2'
                    dfs_cw(cw_graph, nx, ny, 'B')
        else: # 이전색이 R또는 G인경우
            if 0 <= nx < n and 0 <= ny < n and (graph[nx][ny] == 'R' or graph[nx][ny] == 'G'):
                if graph[nx][ny] == 'R':
                    graph[nx][ny] = '0'
                    dfs_cw(cw_graph, nx, ny, 'R')
                elif graph[nx][ny] == 'G':
                    graph[nx][ny] = '1'
                    dfs_cw(cw_graph, nx, ny, 'G')
                elif graph[nx][ny] == 'B':
                    graph[nx][ny] = '2'
                    dfs_cw(cw_graph, nx, ny, 'B')

for x in range(n):
    for y in range(n):
        if graph[x][y].isalpha():
            if graph[x][y] == 'R':
                normal_cnt += 1
                graph[x][y] = '0'
                dfs_normal(graph, x, y, 'R')
            elif graph[x][y] == 'G':
                normal_cnt += 1
                graph[x][y] = '1'
                dfs_normal(graph, x, y, 'G')
            elif graph[x][y] == 'B':
                normal_cnt += 1
                graph[x][y] = '2'
                dfs_normal(graph, x, y, 'B')

for x in range(n):
    for y in range(n):
        if cw_graph[x][y].isalpha():
            if cw_graph[x][y] == 'R':
                cw_cnt += 1
                cw_graph[x][y] = '0'
                dfs_cw(cw_graph, x, y, 'R')
            elif cw_graph[x][y] == 'G':
                cw_cnt += 1
                cw_graph[x][y] = '1'
                dfs_cw(cw_graph, x, y, 'G')
            elif cw_graph[x][y] == 'B':
                cw_cnt += 1
                cw_graph[x][y] = '2'
                dfs_cw(cw_graph, x, y, 'B')

print(normal_cnt, cw_cnt)