[Python Gold V 10026] 적록색약

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

10026번: 적록색약

 

시간 제한	메모리 제한
1초	128MB

 

문제

• 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.
• 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)
• 예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

 

• 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)
• 그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
• 둘째 줄부터 N개 줄에는 그림이 주어진다.

 

출력

• 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

 

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색
• 깊이 우선 탐색

 

---

 📖 Code

N = int(input())
check = False
check2 = False
check_x, check_y = [],[]
a,b = 0,0
lst = [[0 for j in range(N)] for i in range(N)]
for i in range(N):
    rgb = input()
    for j in range(N):
        if check == False:
            check_x.append(i)
            check_y.append(j)
            check = True
        lst[i][j] = rgb[j]
R, G, B, RG= 0,0,0,0
dx = [1,-1,0,0]
dy = [0,0,1,-1]



def search(color):
    global R,G,B,RG
    search_check = False
    while check_x:
        x = check_x.pop()
        y = check_y.pop()
        if color == "R" or color == "G":
            lst[x][y] = "RG"
            search_check =True
        else:
            lst[x][y] = "C"
            search_check =True
        for i in range(4):
            if N-1 >=x+dx[i]>=0 and N-1 >= y+dy[i] >= 0:                
                if lst[x+dx[i]][y+dy[i]] == color:
                    check_x.append(x+dx[i])
                    check_y.append(y+dy[i])
                    if color == "R" or color == "G":
                        lst[x+dx[i]][y+dy[i]] = "RG"
                        search_check =True
                    else :
                        lst[x+dx[i]][y+dy[i]] = "C"
                        search_check =True
    if search_check ==True:
        if color == "R":
            R+=1
        elif color == "B":
            B+=1
        elif color == "G":
            G+=1
        elif color == "RG":
            RG+=1
    for i in range(N):
        if lst[i].count("C") != N:
            for j in range(N):
                if "R" == lst[i][j] or "B" == lst[i][j] or "G" == lst[i][j]:
                    check_x.append(i)
                    check_y.append(j)
                    return search(lst[i][j])
                elif "RG" == lst[i][j] and check2 ==True:
                    check_x.append(i)
                    check_y.append(j)
                    return search(lst[i][j])
                


search(lst[check_x.pop()][check_y.pop()])
check2 = True
search("RG")

print(R+G+B, end=" ")
print(RG+B)

 ✅ Comment

총 두번 탐색을 진행한다.

첫번째 탐색은.

R , G , B 각각의 값을 알아내고.

R , G 의 경우 RG 로 바꿔준다.

B 일경우 탐색 완료 표시를 위해 C로 바꿔준다.

 

두번째 탐색으로 RG 값만 다시 탐색해주면

밑의 두값을 구할수있다.

R + B + G / RG + B