[백준] 10026번 적록색약[Python] - BFS

 

 

색별로 구분된 구역의 개수를 구하는 문제

3색을 기준으로 구분된 구역과

적록색약에 의해 빨간색과 초록색을 같은 색으로 볼 때, 구분되는 구역의 개수를 각각 구해야 합니다.

RRRBB GGBBB BBBRR BBRRR RRRRR

 

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R$($빨강$)$, G$($초록$)$, B$($파랑$)$ 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. $($색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다$)$

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. $($빨강 2, 파랑 1, 초록 1$)$ 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. $($빨강-초록 2, 파랑 1$)$

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

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

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

출력

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

 

먼저 R, G, B 색의 구역별 개수를 세는 코드를 만들어 봤습니다.

 

import sys
from collections import deque

N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    graph.append(list(sys.stdin.readline().rstrip()))

count_dict = {s: 0 for s in ("R", "G", "B")}

def section(y0, x0):
    color = graph[y0][x0]
    graph[y0][x0] = False
    q = deque([(y0, x0)])
    # 상하좌우로 움직일 때, 범위 내, 방문 x, 같은 색 >>> 탐색할 목록에 추가, 방문 표시 
    while q:
        y, x = q.popleft()
        if 0 < y and graph[y - 1][x]:
            if graph[y - 1][x] == color:
                q.append((y - 1, x))
                graph[y - 1][x] = False
        if y + 1 < N and graph[y + 1][x]:
            if graph[y + 1][x] == color: 
                q.append((y + 1, x))
                graph[y + 1][x] = False
        if 0 < x and graph[y][x - 1]:
            if graph[y][x - 1] == color:
                q.append((y, x - 1))
                graph[y][x - 1] = False
        if x + 1 < N and graph[y][x + 1]:
            if graph[y][x + 1] == color: 
                q.append((y, x + 1))
                graph[y][x + 1] = False

# 모든 좌표를 탐색하면서 방문 안한 좌표가 포함된 구역 탐색
for i in range(N):
    for j in range(N):
        if graph[i][j]:
            count_dict[graph[i][j]] += 1
            section(i, j)

print(sum(count_dict.values()))

 

import sys

N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    s = sys.stdin.readline().rstrip()
    graph.append(list(s))

c1, c2 = 0, 0
visited1 = [[False] * N for _ in range(N)]
visited2 = [[False] * N for _ in range(N)]
d = ((-1, 0), (1, 0), (0, -1), (0, 1)) # 상, 하, 좌, 우

# 아래 두 함수는 범위 내, 방문 안한 좌표에 대해서
# three > 같은 색일 때 탐색을 계속 이어가거나
# two > 파랑색 구역만 탐색하거나 파랑 아닌 색만 탐색한다.
def three(y0, x0):
    color = graph[y0][x0]
    visited1[y0][x0] = True
    q = [(y0, x0)]
    while q:
        y, x = q.pop()
        for dy, dx in d:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N and not visited1[ny][nx] and graph[ny][nx] == color:
                q.append((ny, nx))
                visited1[ny][nx] = True

def two(y0, x0):
    color = graph[y0][x0]
    visited2[y0][x0] = True
    q = [(y0, x0)]
    while q:
        y, x = q.pop()
        for dy, dx in d:
            ny, nx = y + dy, x + dx
            if 0 <= ny < N and 0 <= nx < N and not visited2[ny][nx] and (graph[ny][nx] == 'B' == color or graph[ny][nx] != 'B' and color != 'B'):
                q.append((ny, nx))
                visited2[ny][nx] = True

# 모든 좌표에 대해서 방문 안한 좌표 탐색
for i in range(N):
    for j in range(N):
        if not visited1[i][j]:
            c1 += 1
            three(i, j)
        if not visited2[i][j]:
            c2 += 1
            two(i, j)

print(c1, c2)

 

어떤 색을 key, 그 색과 다른 색의 목록을 value로 저장한 딕셔러니를 활용한 코드

다른 색 목록을 작성함으로써 R과 G를 같은 색으로 인식하도록 할 수 있음.

import sys

N = int(sys.stdin.readline())
graph = []
for _ in range(N):
    s = sys.stdin.readline().rstrip()
    graph.append(list(s))

# 다른 색을 value 값으로 저장한 딕셔너리를 정의합니다.
three_dic = {"R": ("G", "B"), "G": ("R", "B"), "B": ("R", "G")}
two_dic = {"R": ("B"), "G": ("B"), "B": ("R", "G")}

d = ((-1, 0), (1, 0), (0, -1), (0, 1))	# 상, 하, 좌, 우

def bfs(dic):
    visited = [[False] * N for _ in range(N)]
    c = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j]:
                c += 1  # 발견 안 한 구역 개수 + 1
                color = graph[i][j]  # 현재 색상 저장
                visited[i][j] = True  # 방문 표시
                q = [(i, j)]  # 방문할 리스트
                while q:
                    y, x = q.pop()  # 선입선출을 굳이 할 필요가 없어서 큐나 pop(0) 사용 x
                    for dy, dx in d:
                        ny, nx = y + dy, x + dx  # 이동할 위치
                        # 범위 내에 있고, 아직 방문 x, 색상이 현재 색상과 같을 때:
                        if 0 <= ny < N and 0 <= nx < N and not visited[ny][nx] and graph[ny][nx] not in dic[color]:
                            q.append((ny, nx))  # 탐색할 목록에 추가
                            visited[ny][nx] = True  # 방문 표시
    return c  # 구역 개수 반환

print(bfs(three_dic), bfs(two_dic))

 

예제 입력 1 

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

예제 출력 1 

4 3​