[BOJ] 10026. 적록색약

문제

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

• N*N 크기의 그리드 각 칸에 RGB 중 하나를 색칠한 그림
  • 그림은 몇 개의 구역으로 나뉘는 데 구역은 같은 색으로 이뤄져있음
  • 같은 색상이 인접한 경우 두 글자는 같은 구역 = 같은 영역

 

---

 

주요 아이디어

• DFS 문제라고 하는데 BFS로도 풀 수 있을 것 같아서 이걸로 풀었다!
• BFS로 인접 노드를 순회하면서, 색깔 같을 때마다 방문하고 queue 순회를 끝내면 +1 (구역 추가)
• 대신 적록색약과 정상인의 기준을 다르게 해주어야 하므로, flag 변수를 통해 구분을 주었다

 

---

 

코드 구현 (Python 3)

 

from collections import deque

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

normal_visited = []; color_visited = []
direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
result, result_c = 0, 0

def bfs(sy, sx, flag):
    global graph, n, normal_visited, color_visited
    queue = deque()
    queue.append((sy, sx))

		# 정상인, 색약 구분
    if flag == 'normal':
        visited = normal_visited
    else:
        visited = color_visited

    visited.append((sy, sx))

    while queue:
        y, x = queue.popleft()

        for d in direction:
            ny, nx = y + d[0], x + d[1]
            if 0 <= ny < n and 0 <= nx < n and (ny, nx) not in visited:
                if graph[y][x] == graph[ny][nx]:
                    visited.append((ny, nx))
                    queue.append((ny, nx))
                    
                # 색약의 경우 RG 구분 X
                elif flag == 'color' and (graph[y][x] + graph[ny][nx] == 'RG' or graph[y][x] + graph[ny][nx] == 'GR'):
                    visited.append((ny, nx))
                    queue.append((ny, nx))
    
    return visited


for i in range(n):
    for j in range(n):
        if (i, j) not in normal_visited:
            normal_visited = bfs(i, j, 'normal')
            result += 1
        if (i, j) not in color_visited:
            color_visited = bfs(i, j, 'color')
            result_c += 1


print(result, result_c)

 

 

---

 

제출 결과