백준/ Gold 5 문제 , 백준 파이썬 10026 , 적록색약 [BFS]

백준/ Gold 5 문제 , 백준 파이썬 10026 , 적록색약 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
세개를 분류 하는건 쉬웠는데, 이후에 두개로 분류할때가 약간 까다로웠다. 

 

<문제 출처>

 

https://www.acmicpc.net/problem/10026

10026번: 적록색약

------------------------------------------------------------------------------------------------------------------------------

 

<접근 방법>

 

1. R,G,B 각각의 구역을 카운트해주고 저장

 

2. 위에서 R,G 는 X , B는 Y 로 바꿔줘서 첫번째 결과를 도출해낸 이후의 표는 X와 Y로 두개로만 분류될 수 있게 새로 만들어줬다.

(R하고 G를 같다고 보기때문에 같은 문자로 변경시켰다.)

 

3. 두번째 결과는 X와 Y의 영역들을 카운트해줬다.

 

 

 

 

 

 

 

 

 

 

------------------------------------------------------------------------------------------------------------------------------

정답

 

 

 

from collections import deque

vertical=[1,-1,0,0]
parallel=[0,0,1,-1]
dq=deque()
N=int(input())
RGB=[]
for _ in range(N):
    RGB.append(list(input()))
    
def bfs(word):
    global cnt
    while dq:
        x,y=dq.popleft()
        for i in range(4):
            move_x=x+vertical[i]
            move_y=y+parallel[i]
            if 0<=move_x<N and 0<=move_y<N:
                if check==True:
                    if RGB[move_x][move_y]==word:
                        dq.append([move_x,move_y])
                        if word!='B':
                            RGB[move_x][move_y]='X'
                        elif word=='B':
                            RGB[move_x][move_y]='Y'
                else:
                    if RGB[move_x][move_y]==word:
                        dq.append([move_x,move_y])
                        if word=='X':
                            RGB[move_x][move_y]='O'
                        elif word=='Y':
                            RGB[move_x][move_y]='O'
    cnt+=1  
# 적록색약 아닌사람
cnt=1
check=True
for i in range(N):
    for j in range(N):
        if RGB[i][j]=='R':
            RGB[i][j]='X'
            dq.append([i,j])
            bfs('R')
        if RGB[i][j]=='G':
            RGB[i][j]='X'
            dq.append([i,j])
            bfs('G')
        if RGB[i][j]=='B':
            RGB[i][j]='Y'
            dq.append([i,j])
            bfs('B')
answer=[]
answer.append(cnt-1)
# 적록색약인 사람
cnt=1
check=False
for i in range(N):
    for j in range(N):
        if RGB[i][j]=='X':
            RGB[i][j]='O'
            dq.append([i,j])
            bfs('X')
        if RGB[i][j]=='Y':
            RGB[i][j]='O'
            dq.append([i,j])
            bfs('Y')
# B가 없는 경우 방지
if cnt==1:
    cnt=2
answer.append(cnt-1)
print(*answer)