[백준] 적록색약 (10026번)

난이도 : Gold5
Link : https://www.acmicpc.net/problem/10026
Tag : 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색
풀이일자 : 2024년 9월 12일

📌 문제 탐색하기

N : 그림의 크기 (N x N)
이 문제는 그리드 내에서 R,G,B의 집합의 갯수를 구하는 문제이다.
단 적록 색약인 경우도 생각해야 한다.

이 문제는 다른 지도 문제와 마찬가지로 BFS 섬의 개수 구하는 방법대로 접근하면 될 것으로 보인다.

가능한 시간복잡도

BFS함수를 2가지로 나눌 생각이다.
가능한 시간복잡도는 NxN을 완전 탐색하는 경우로 N의 크기는 1<=N<=100이므로 100 x 100 = 10000 이어서 충분히 탐색가능하다.
단) BFS를 두번 사용하면서 두번 완전 탐색 되는 경우만 방지하면 될것으로 보인다.

📌 문제 접근 방법

1. BFS를 이용하여 RGB의 집합의 개수를 파악할 예정이다.
2. BFS에 조건을 추가한 적록색약 전용 RGB의 집합의 개수를 파악할 예정이다.
   • 적록색약 전용 BFS는 탐색하고 있는 RGB중 R과 G일 경우에 주변에 R과 G를 탐색하고 있는 RGB로 인식하게한다.
3. 각 집합의 개수를 더해서 출력할 예정이다.

📌 코드 설계하기

1. Grid의 크기를 설정할 N을 입력받는다.

2. grid와 grid2를 입력 받는다

   • grid를 입력받아 DeepCopy를 통해 grid2에 저장한다
   • grid는 정상인 grid2는 색약 사람이 측정할 그리드 공간이다.

3. RGB 집합을 계산할 변수 6개를 생성한다

   cnt_R, cnt_G, cnt_B = 0, 0, 0
   cnt_R2, cnt_G2, cnt_B2 = 0, 0, 0
   R,G,B는 정상인의 개수 R2,G2,B2는 색약인구의 개수

4. BFS 함수를 생성한다. (정상인)

def BFS(x,y, RGB): #정상인
    queue = deque([(x,y)])
    grid[y][x] = 'A'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<n and grid[ny][nx]== RGB:
                queue.append((nx,ny))
                grid[ny][nx] = 'A'

5. BFS 함수를 생성한다. (색약) - R과 G일 경우 주변의 G와 R을 개수를 세고 있는 RGB로 바꾼다.

def BFS_rg(x,y,RGB): #적녹 색맹
    queue = deque([(x,y)])
    grid2[y][x] = 'A'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if (RGB == 'R' or RGB == 'G') and 0<=nx<n and 0<=ny<n and (grid2[ny][nx]=='G' or grid2[ny][nx]=='R'):
                queue.append((nx,ny))
                grid2[ny][nx] = 'A'
            elif 0<=nx<n and 0<=ny<n and grid2[ny][nx] == RGB:
                queue.append((nx,ny))
                grid2[ny][nx] = 'A'

6. grid와 grid2를 탐색하며 두 BFS를 사용한다.
7. answer에는 정상인의 집합 개수를 , answer2에는 색약인의 집합 개수를 저장해 출력한다.

📌 시도 회차 수정 사항

📌 정답 코드

from collections import deque
import copy

n = int(input())
grid = [list(input()) for _ in range(n)]
grid2 = copy.deepcopy(grid)
m = len(grid[0])
cnt_R, cnt_G, cnt_B = 0, 0, 0
cnt_R2, cnt_G2, cnt_B2 = 0, 0, 0
answer = 0

def BFS(x,y, RGB): #정상인
    queue = deque([(x,y)])
    grid[y][x] = 'A'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if 0<=nx<n and 0<=ny<n and grid[ny][nx]== RGB:
                queue.append((nx,ny))
                grid[ny][nx] = 'A'

def BFS_rg(x,y,RGB): #적녹 색맹
    queue = deque([(x,y)])
    grid2[y][x] = 'A'
    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if (RGB == 'R' or RGB == 'G') and 0<=nx<n and 0<=ny<n and (grid2[ny][nx]=='G' or grid2[ny][nx]=='R'):
                queue.append((nx,ny))
                grid2[ny][nx] = 'A'
            elif 0<=nx<n and 0<=ny<n and grid2[ny][nx] == RGB:
                queue.append((nx,ny))
                grid2[ny][nx] = 'A'

for i in range(n): #세로 y
    for j in range(m): #가로 x
        if grid[i][j] == 'R':
            RGB = 'R'
            cnt_R += 1
            BFS(j,i,RGB)
        elif grid[i][j] == 'G':
            RGB = 'G'
            cnt_G += 1
            BFS(j,i,RGB)
        elif grid[i][j] == 'B':
            RGB = 'B'
            cnt_B += 1
            BFS(j,i,RGB)

        if grid2[i][j] == 'R':
            RGB = 'R'
            cnt_R2 += 1
            BFS_rg(j,i,RGB)
        elif grid2[i][j] == 'G':
            RGB = 'G'
            cnt_G2 += 1
            BFS_rg(j,i,RGB)
        elif grid2[i][j] == 'B':
            RGB = 'B'
            cnt_B2 += 1
            BFS_rg(j,i,RGB)

answer = cnt_R + cnt_G + cnt_B
answer2 = cnt_R2 + cnt_G2 + cnt_B2
print(answer, answer2)