[백준/python] 10026번 적록색약

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

10026번: 적록색약

알고리즘

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

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

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

 

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)