문제
적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
예를 들어, 그림이 아래와 같은 경우에
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.
풀이
우선 제일 먼저 해결해야 할 문제는 RGB이 세가지 색이 어떻게 그룹화되어 있는지 확인하는 것이다.
그러려면 우선 BFS를 사용해 모든 이차원리스트를 순회해주면 되는데 이때 함수 내부로 들어온 시작점의 색깔을 구해주고 4방향에 대해 색깔이 같다면 queue에 넣고 방문처리를 해준다. 물론 새로 이동할 방향이 리스트를 초과하지는 않는지 검사하는 것도 잊으면 안된다.
그렇게 함수가 실행되고나면 visited 테이블에 같은 색깔인 모든 값들을 방문처리 해줄텐데 그러면 아래에서 이중 포문 순회를 통해서 이미 방문처리된 값들을 함수값에 인자로 넣어주지 않아도 되고 함수가 한번 실행되고 True를 반환했다면 그룹이 하나 있다는 것이므로 cnt에 1을 더해준다.
이제 적록색약의 입장에서 갯수를 세어야 하는데 나는 BFS 함수 하나 더 만들어보는 연습 겸 해서 함수를 하나더 만들었다.
if (cur_color == "R" or cur_color == "G") and\
(graph[next_row][next_col] == "R" or graph[next_row][next_col] == "G"):
r_g_weekness_visited[next_row][next_col] = 1
r_g_queue.append((next_row, next_col))
elif cur_color == graph[next_row][next_col]:
r_g_weekness_visited[next_row][next_col] = 1
r_g_queue.append((next_row, next_col))다른 함수에서 같은 색깔이면 큐에 넣는 로직을 위 로직으로 변경만 해주면 R과 G를 같은 색깔처럼 취급해줄 수 있다.
거기다 B일 때는 같은 색깔이라면 넣어주는 부분도 필요하기에 원래의 로직을 elif로 넣어주었다.
from collections import deque
import sys
def get_r_g_weakeness_group(row, column):
r_g_queue = deque()
r_g_queue.append((row, column))
cur_color = graph[row][column]
while r_g_queue:
cur_row, cur_col = r_g_queue.popleft()
for direction in directions:
next_row = cur_row + direction[0]
next_col = cur_col + direction[1]
if next_row < 0 or next_row >= N or next_col < 0 or next_col >= N:
continue
if r_g_weekness_visited[next_row][next_col]: continue
if (cur_color == "R" or cur_color == "G") and\
(graph[next_row][next_col] == "R" or graph[next_row][next_col] == "G"):
r_g_weekness_visited[next_row][next_col] = 1
r_g_queue.append((next_row, next_col))
elif cur_color == graph[next_row][next_col]:
r_g_weekness_visited[next_row][next_col] = 1
r_g_queue.append((next_row, next_col))
return True
def get_group(row, column):
queue = deque()
queue.append((row, column))
cur_color = graph[row][column]
while queue:
cur_row, cur_col = queue.popleft()
for direction in directions:
next_row = cur_row + direction[0]
next_col = cur_col + direction[1]
if next_row < 0 or next_row >= N or next_col < 0 or next_col >= N:
continue
if group_visited[next_row][next_col]: continue
if cur_color == graph[next_row][next_col]:
group_visited[next_row][next_col] = 1
queue.append((next_row, next_col))
return True
if __name__ == '__main__':
sys.stdin = open('', 'r')
N = int(input())
graph = [input() for _ in range(N)]
r_g_weekness_visited = [[0] * N for _ in range(N)]
group_visited = [[0] * N for _ in range(N)]
directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
r_g_cnt = 0
cnt = 0
for i in range(N):
for j in range(N):
if not group_visited[i][j] and get_group(i, j):
cnt+=1
if not r_g_weekness_visited[i][j] and get_r_g_weakeness_group(i, j):
r_g_cnt+=1
print(f"{cnt} {r_g_cnt}")