10026 적록색약

1. 문제

문제는 링크를 들어가면 볼 수 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import copy
import sys
read = sys.stdin.readline
from collections import deque

N = int(read())
graph = []
for _ in range(N):
    temp = list(read())
    temp.pop()
    graph.append(temp)

another_graph = copy.deepcopy(graph)

# 일반인 BFS와 색맹 BFS를 구분지어서 만드는게 편할 듯.
# 상 하 좌 우
dx = [0,0,-1,1]
dy = [-1,1,0,0]
#
def general_bfs(graph,y,x,state):
    # complete 처리하기.
    graph[y][x] = "C"
    q = deque()
    q.append([y,x])
    while q :
        now = q.popleft()
        # 4방향을 보자.
        for i in range(4):
            ny = now[0] + dy[i]
            nx = now[1] + dx[i]
            # 그래프의 범위를 넘어가지 않게 조절
            if nx<0 or ny<0 or nx >= N or ny >= N :
                continue
            if graph[ny][nx] == state :
                # 단순 방문 처리만 해주면된다.
                graph[ny][nx] = "C"
                q.append([ny,nx])

def another_bfs(graph,y,x,state):
    # complete 처리하기.
    graph[y][x] = "C"
    q = deque()
    q.append([y,x])
    while q :
        now = q.popleft()
        # 4방향을 보자.
        for i in range(4):
            ny = now[0] + dy[i]
            nx = now[1] + dx[i]
            # 그래프의 범위를 넘어가지 않게 조절
            if nx<0 or ny<0 or nx >= N or ny >= N :
                continue

            # R,G를 같게 보고 B를 따로 보기위한 조건문 처리
            if state == "R" or state == "G" :
                if graph[ny][nx] == "R" or graph[ny][nx] == "G":
                    # 단순 방문 처리만 해주면된다.
                    graph[ny][nx] = "C"
                    q.append([ny, nx])
            else :
                if graph[ny][nx] == state:
                    # 단순 방문 처리만 해주면된다.
                    graph[ny][nx] = "C"
                    q.append([ny, nx])
# 그래프를 순차적으로 탐방하면서 R,G,B인 경우 bfs를 들어가고,
# bfs에선 탐방한 곳을 C로 바꿔야할듯.
# cnt를 둬서 구역의 수를 카운트 할 것

cnt = 0
another_cnt = 0
for y in range(N):
    for x in range(N):
        general_state = graph[y][x]
        if general_state != "C" : # 아직 방문하지 않았을땐
            general_bfs(graph,y,x,general_state)
            cnt += 1
        another_state = another_graph[y][x]
        if another_state != "C" :
            another_bfs(another_graph,y,x,another_state)
            another_cnt += 1
print(cnt,another_cnt)

3. 문제 풀이

이 문제는 가장 기본적인 BFS문제여서 어렵진 않은데 R,G를 같이 봐야하는 조건 때문에 조금 생각해야했다. 솔직히 BFS 함수 하나로 구현할 수 있을 것 같은데, 어렵게 풀지 않으려고 했기에 그냥 함수를 2개를 써서 구현했다.