[백준/10026] 적록색약 | 그래프 영역 구별, 같은 조건일 때 처리

https://www.acmicpc.net/problem/10026

10026번: 적록색약

이 문제는 조금 개인적인 일화가 있는데,, 작년 2학기에 교내 알고리즘 대회를 준비하면서 이 문제를 접하고 엄청 허둥지둥 거리다가 포기한 기억이 있다. 이 문제 구현을 어떻게 할지 구상해보면서 문득 저번 학기가 떠올랐는데, 방학 동안 꾸준히 공부한 보람이 조금이나마 있어서 다행이다..! 

 

알고리즘

bfs, dfs는 알고리즘이 정해져 있어서 막 구현이 어려운 문제는 아니다.

하지만 이 문제를 어떻게 그래프로 탐색하고 풀어나갈지 생각하는 게 쉽지는 않다.

 

요구 조건이 적록색약이 보는 사람과 아닌 사람이 보는 구역의 수다.

여기서 말하는 구역의 수란 같은 색으로 이루어진 부분이다.

따라서 상하좌우로 인접한 글자들이 같은 색이어야 같은 구역이고, 다른 색이면 다른 구역이다.

 

bfs로 방문을 하지 않은 곳을 방문해주면서, 그래프의 상하좌우를 탐색했을 때 이미 방문한 곳이라면 방문 표시를 해준다. 

방문 표시가 된 곳부터 다시 탐색을 하면서 주변에 같은 색상이 있는지 탐색하고, 없으면 다시 bfs를 수행한다.

전체 코드

from collections import deque

n = int(input()) 
graph = [list(input()) for _ in range(n)]

dir = [(0,-1),(0,1),(1,0),(-1,0)]
q = deque()

def bfs(x,y) : 
    q.append((x,y))
    v[x][y] = True
    
    while q : 
        x, y = q.popleft()
        for dx, dy in dir : 
            nx, ny = x+dx, y+dy
            
            # 범위에 맞고, 방문 안했을 경우
            if 0 <= nx < n and 0 <= ny < n and v[nx][ny] == False : 
                # ***  같은 색이라면 *** 
                if graph[nx][ny] == graph[x][y] : 
                    v[nx][ny] = True # 방문 표시
                    q.append((nx,ny))
               
# 적록색약이 아닌 경우
x = 0
v = [[False]*n for _ in range(n)]

for i in range(n):
    for j in range(n) : 
        if v[i][j] == False: 
            bfs(i,j)
            x += 1
                           
# 적록색약인 경우 G == R 
o = 0
v = [[False]*n for _ in range(n)]

for i in range(n) : 
    for j in range(n) : 
        if graph[i][j] == 'G' : graph[i][j] = 'R' 

for i in range(n):
    for j in range(n):
        if v[i][j] == False:
            bfs(i,j)
            o += 1
            
print(x, o)