[백준 10026] 적록색약

문제

크기가 NxN의 각 칸에 R, G, B 색 정보가 담겨져있다.

적록색약인 사람은 R과 G를 구분하지 못하고 하나의 색으로 본다.

이때 각각의 색 구역을 적록색약이 아닌사람과 적록색약인 사람이 몇 개의 구역으로 보는지 구하라.

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

---

접근

적록색약인 사람과 아닌 사람에 따라 다른 BFS로 하려고했지만 코드가 너무 길어졌다. 그래서 적록색약이 아닌 사람의 구역을 먼저 구한 다음에 그림판에서 G를 R로 바꿔주어 적록색약인 사람의 구역을 구하도록 하였다.

 

구현

그림판의 정보를 입력받는다.

N = int(input())
color_map = [list(map(str, input().rstrip())) for _ in range(N)]

 

먼저 적록색약이 아닌 사람에 대해서 BFS를 진행하고 BFS가 진행한 만큼이 적록색약이 아닌 사람이 보는 구역이 된다.

이후에 그림판에서 G를 R로 변경한다.

result = []

cnt = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            cnt += 1
            bfs(y, x)
result.append(cnt)

for y in range(N):
    for x in range(N):
        if color_map[y][x] == 'G':
            color_map[y][x] = 'R'

 

이후에 적록색약인 사람이 보는 그림판으로 BFS를 실행하여 구역을 구한다.

cnt = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            cnt += 1
            bfs(y, x)
result.append(cnt)

 

BFS에서는 해당좌표의 색을 통해 같은 색을 찾아주고 방문표시를 해준다. 

def bfs(y, x):
    q = deque()
    q.append((y, x))
    color = color_map[y][x]
    visited[y][x] = True

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]


    while q:
        cy, cx = q.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and (not visited[ny][nx]):
                if color_map[ny][nx] == color:
                    q.append((ny, nx))
                    visited[ny][nx] = True

---

전체 코드

import sys
from _collections import deque
input = sys.stdin.readline

def check_range(y, x):
    return (y>=0 and y<N) and (x>=0 and x<N)

def bfs(y, x):
    q = deque()
    q.append((y, x))
    color = color_map[y][x]
    visited[y][x] = True

    dy = [1, -1, 0, 0]
    dx = [0, 0, 1, -1]


    while q:
        cy, cx = q.popleft()

        for d in range(4):
            ny = cy + dy[d]
            nx = cx + dx[d]
            if check_range(ny, nx) and (not visited[ny][nx]):
                if color_map[ny][nx] == color:
                    q.append((ny, nx))
                    visited[ny][nx] = True


N = int(input())
color_map = [list(map(str, input().rstrip())) for _ in range(N)]

result = []

cnt = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            cnt += 1
            bfs(y, x)
result.append(cnt)

for y in range(N):
    for x in range(N):
        if color_map[y][x] == 'G':
            color_map[y][x] = 'R'

cnt = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for y in range(N):
    for x in range(N):
        if not visited[y][x]:
            cnt += 1
            bfs(y, x)
result.append(cnt)



print(*result)