적록 색약 문제는 일반인이 봤을때의 구역과 적록색맹을 가지고 있는 사람이 봤을떄의 구역의 수를 나타내는 문제이다.
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR
이런 그래프가 있을때 일반인이라면 R,G,B를 각각 구분 가능하기 떄문에 R구역 2개 G 구역 1개 B구역 1개로 총 4개의 구역이 있음을 알수있다.
하지만 적록색맹을 가지고 있는 사람은 R과 G를 구분 불가하기떄문에 R,G 구역 2개 B 구역 1개로 총 3개의 구역이 있음을 알수있는것이다.
내 처음 생각은 기존 BFS 문제처럼 처음부터 마지막 인덱스까지 전체 BFS 를 돌리기로했다.
그러면 구역이 나올꺼니까
import sys
from collections import deque
dir=[[0,1],[1,0],[0,-1],[-1,0]]
n=int(sys.stdin.readline())
mapGraph=[list(sys.stdin.readline().rstrip()) for i in range(n)]
visited=[[0 for i in range(n)]for i in range(n)]
RGvisited=[[0 for i in range(n)]for i in range(n)]
def BFS_iter(x,y):
queue = deque()
queue.append((x,y))
while queue:
dx,dy=queue.popleft()
for i in range(4):
nx=dx+dir[i][0]
ny=dy+dir[i][1]
if nx >= 0 and nx < n and ny >= 0 and ny < n:
if mapGraph[dx][dy] == "R" or mapGraph[dx][dy] == "G":
if visited[nx][ny] == 0 and (mapGraph[nx][ny] == "R" or mapGraph[nx][ny] == "G"):
visited[nx][ny] = 1
queue.append((nx, ny))
elif mapGraph[dx][dy] == "B":
if visited[nx][ny] == 0 and mapGraph[nx][ny] == "B":
visited[nx][ny] = 1
queue.append((nx, ny))
return 1
def BFS_normal(x,y):
queue = deque()
queue.append((x,y))
while queue:
dx,dy=queue.popleft()
for i in range(4):
nx=dx+dir[i][0]
ny=dy+dir[i][1]
if nx>=0 and nx<n and ny>=0 and ny<n:
if mapGraph[dx][dy] == mapGraph[nx][ny]:
if RGvisited[nx][ny] == 0:
RGvisited[nx][ny] = 1
queue.append((nx, ny))
return 1
rgcount=0
count=0
for i in range(n):
for j in range(n):
if visited[i][j]==0 and BFS_iter(i,j)==1:
visited[i][j]=1
count+=1
if RGvisited[i][j]==0 and BFS_normal(i,j)==1:
RGvisited[i][j]=1
rgcount+=1
print(rgcount,count)그렇게 나온 코드가 이거다.
일반인과, 적록색맹을 가진 사람을 구분해줘야 하기에 나는 2개의 함수를 쓸꺼라 생각했지만
태곤이랑 시윤이 보경이 코드보고 감탄을 할수밖에 없었다..
일반인 함수에서는 R는 R만 B는 B만 G는 G만 탐색을 시작하게 설정을 해주는것 까진 비슷했는데 이제 적록색맹은 R과 B를 구분을 못하기에 따로 탐색을 해야했다.
그래서 나는 현재 위치가 R이나 B이면 R와 B만 탐색을 하게 코드를 짰는데 이렇게 되면 위에서 코드를 보다시피 함수는 2개가 되어버리고 간결하지못하고 효율성도 당연하게 안좋아 질것이다.
하지만 태곤이 코드를 보자.
[링크텍스트](https://m.blog.naver.com/PostView.naver?blogId=sloec10&logNo=222836369748&navType=by
import sys
from collections import deque
input = sys.stdin.readline
N = int(input())
graph = [list(input().rstrip()) for _ in range(N)]
queue = deque()
dr = [-1,1,0,0] #4방향
dc = [0,0,-1,1]
def bfs(r,c,s):
global result
queue.append([r,c])
while queue:
x,y = queue.popleft()
visited[x][y] = True
for i in range(4):
nx = x + dr[i]
ny = y + dc[i]
#범위를 벗어나지 않고 방문한적이 없다면
if 0<=nx<N and 0<=ny<N and not visited[nx][ny]:
if graph[nx][ny] == s: #만약 해당 index 색 = 탐색하고자 하는 색
visited[nx][ny] = True
queue.append([nx,ny])
result+=1 #한 구간 탐색 후 증감
for i in range(2): #적록색약이 아닌경우 / 적록색약인 경우
result = 0 #구간 count횟수 초기화
visited = [[False for _ in range(N)] for _ in range(N)] #방문리스트 초기화
for i in range(N):
for j in range(N):
if not visited[i][j]: #방문하지 않았다면
bfs(i,j,graph[i][j]) #그 색을 가지고 탐색시작
print(result)
for i in range(N): #적록색약 R==G -> G->R로 바꾸기
for j in range(N):
if graph[i][j] == 'G':
graph[i][j] = 'R'
태곤이 코드를 보면 같은 함수를 쓰지만 처음 일반인이 보는 구역은 똑같이 탐색을 하지만 한번 탐색을 끝내고 나면 다음 적록색맹 탐색은 G를 다 R로 바꾸어서 탐색을 시작한것이다. 정말,,,감탄,,,
1차원적인 생각을 버리는 연습! 필요!
열심히 하는 우리 화이팅
