프로그래밍 공부/백준 알고리즘
[Python] 10026번 : 적록색약
오구.cpp
2023. 2. 24. 22:40
반응형
문제 3줄 요약
1. 색깔 별 영역을 나눈다.
2. 적록색약은 빨강과 초록을 같은 색으로 인지하여 구역을 나눈다.
3. 일반인이 보는 색깔 별 영역과 적록색약이 보는 색깔 별 영역을 구해라
BFS로 기준으로 잡은 색과 다른 색이 나오면,
다시 돌아가는 방식으로 코드를 작성하였다.
조금 차이점이 있다면,
적록색약일 경우엔 빨강과 초록을 같게 인지하는 조건문을 추가해주었다.
문제가 어렵진 않았지만,
문제를 해결하고 난 후 다른 사람과 코드를 비교해보았을 때,
상하좌우 비교와 구조체 생성을 리스트 하나로 해결하는 코드를 주로 작성하는게 보였다.
지금 나의 코드는 직관적이라고 생각하지만,
코드의 길이가 길고
복잡한 기능이 필요한 BFS, DFS 일 경우
잦은 오류가 발생하는 것 같다.
이후의 DFS, BFS 문제 같은 경우에는 보았던 코드들을 참고해서
풀어갈 예정이다.
작성한 코드를 짧게 설명하자면,
BFS를 위해 덱을 사용하여 선입선출 구조를 사용하고
딕셔너리의 색깔 별 영역의 수를 담도록 하였다.
이후 일반인 일 경우와 적록색약 일 경우의
영역의 합을 구해주었다.
from sys import stdin
from collections import deque
# 좌표 구조체
class XY:
def __init__(self,x,y,color):
self.x = x
self.y = y
self.color = color
def BFS(color_XY,color_dict,feature):
x = color_XY.x
y = color_XY.y
if visited[x][y]:
q.append(color_XY)
visited[x][y] = False
while(len(q) != 0):
color = q.popleft()
i,j,c = color.x,color.y,color.color
# 상하좌우 탐색 + feature==1(적록색약) 일 경우, 빨강 == 초록
if i > 0:
U_c = color_list[i-1][j].color
if ( U_c == c or (feature and (c=="R" or c=="G") and (U_c=="R" or U_c == "G"))) and visited[i-1][j]:
q.append(color_list[i-1][j])
visited[i-1][j] = False
if j > 0:
L_c = color_list[i][j-1].color
if (L_c == c or (feature and (c=="R" or c=="G") and (L_c=="R" or L_c == "G"))) and visited[i][j-1]:
q.append(color_list[i][j-1])
visited[i][j-1] = False
if i+1 < N:
D_c = color_list[i+1][j].color
if (D_c == c or (feature and (c=="R" or c=="G") and (D_c=="R" or D_c == "G"))) and visited[i+1][j]:
q.append(color_list[i+1][j])
visited[i+1][j] = False
if j+1 < N:
R_c = color_list[i][j+1].color
if (R_c == c or (feature and (c=="R" or c=="G") and (R_c=="R" or R_c == "G"))) and visited[i][j+1]:
q.append(color_list[i][j+1])
visited[i][j+1] = False
# 딕셔너리의 색깔 별 영역의 수
color_dict[color_list[x][y].color] += 1
# 초기화
def init():
for i in range(N):
for j in range(N):
visited[i][j] = True
# 일반인
def func_nomal():
for x in range(N):
for y in range(N):
if visited[x][y]:
BFS(color_list[x][y],color_dict,0)
# 적록색약
def func_special():
for x in range(N):
for y in range(N):
if visited[x][y]:
BFS(color_list[x][y],color_dict,1)
if __name__ == "__main__":
N = int(stdin.readline())
visited, color_list = [], []
color_dict = {"R":0, "G":0, "B":0}
for i in range(N):
color_row = []
for j,c in enumerate(list(stdin.readline().strip())):
color_row.append(XY(i,j,c))
color_list.append(color_row)
visited.append([ True for _ in range(N)])
# BFS에 사용할 덱
q = deque()
func_nomal()
# 일반인 영역의 수
print(color_dict["R"]+color_dict["G"]+color_dict["B"], end = " ")
init()
color_dict = {"R":0, "G":0, "B":0}
func_special()
# 적록색약 영역의 수
print(color_dict["R"]+color_dict["G"]+color_dict["B"])
끝!

반응형