📚문제: #10026 적록색약(Gold 5)
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에RRRBB GGBBB BBBRR BBRRR RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1) 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
둘째 줄부터 N개 줄에는 그림이 주어진다.
출력
적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.
예제 입력 1
5 RRRBB GGBBB BBBRR BBRRR RRRRR
예제 출력 1
4 3
아이디어 및 구현
- 적색과 녹색을 구분하지 못하므로 구역의 어느 한가지 색깔로 통일시켜준다.(아래 코드에서는 녹색을 적색으로 변경)
# '녹색'을 '적색'로 바꿉니다.
area_RG_DISORDER = deepcopy(area)
for i in range(N):
for j in range(N):
if area_RG_DISORDER[i][j] == 'G':
area_RG_DISORDER[i][j] = 'R'
else:
continue
- 시작 좌표의 색(적,녹,청) 여부에 따라 BFS 알고리즘을 다르게 작성한다. 예를 들어 시작 좌표가 적색일 때, 이웃 좌표가 적색이여만 방문이 가능하다.
def BFS(graph, v):
# BFS 활용을 위한 큐 선언
queue = deque([v])
# 4방향을 설정합니다.
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
# 시작노드가 R, G, B일 때 각각 분류합니다.
start_r, start_c = v
if graph[start_r][start_c] == 'R':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'R'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'R':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)
elif graph[start_r][start_c] == 'G':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'G'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'G':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)
elif graph[start_r][start_c] == 'B':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'B'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'B':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)전체 코드
import sys
from collections import deque
from copy import deepcopy
# N이 주어집니다.
N = int(sys.stdin.readline().rstrip())
# 색깔 영역
area = []
# 그림이 주어집니다.
for _ in range(N):
area.append(list(sys.stdin.readline().rstrip()))
def BFS(graph, v):
# BFS 활용을 위한 queue 선언
queue = deque([v])
# 4방향을 설정합니다.
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
# 시작노드가 R, G, B일 때 각각 분류합니다.
start_r, start_c = v
if graph[start_r][start_c] == 'R':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'R'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'R':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)
elif graph[start_r][start_c] == 'G':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'G'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'G':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)
elif graph[start_r][start_c] == 'B':
# queue가 차있을 동안 계속 반복
while queue:
# queue에서 좌표를 뽑습니다.
r, c = queue.popleft()
# 방문처리합니다.
graph[r][c] = 'v'
# 4방향 이동 시도
for i in range(4):
move_r = r + dr[i]
move_c = c + dc[i]
# 주어진 그래프를 벗어나지 않으면서 이동하려는 좌표가 'B'일 때를 탐색합니다.
if 0 <= move_r <= N-1 and 0 <= move_c <= N-1:
if graph[move_r][move_c] == 'B':
# 방문처리합니다.
graph[move_r][move_c] = 'v'
# 새로운 좌표를 queue에 추가합니다.
new_loc = [move_r, move_c]
queue.append(new_loc)
# 정상, 적록색약을 위한 영역을 만들기 위해 복사합니다.
area_NORMAL = deepcopy(area)
area_RG_DISORDER = deepcopy(area)
# 'G'를 'R'로 바꿉니다.
for i in range(N):
for j in range(N):
if area_RG_DISORDER[i][j] == 'G':
area_RG_DISORDER[i][j] = 'R'
else:
continue
# 독립된 영역을 계산하기 위한 변수를 초기화 해줍니다.
NORMAL_CNT, RG_DISORDER_CNT = 0, 0
for i in range(N):
for j in range(N):
if area_NORMAL[i][j] == 'R' or area_NORMAL[i][j] == 'G' or area_NORMAL[i][j] == 'B':
start = [i, j]
BFS(area_NORMAL, start)
NORMAL_CNT += 1
else:
continue
for i in range(N):
for j in range(N):
if area_RG_DISORDER[i][j] == 'R' or area_RG_DISORDER[i][j] == 'B':
start = [i, j]
BFS(area_RG_DISORDER, start)
RG_DISORDER_CNT += 1
else:
continue
print(NORMAL_CNT, RG_DISORDER_CNT)