[파이썬] 백준 10026 : 적록색약 (골드5)

[파이썬] 백준 10026 : 적록색약  (골드5)

 

10026번: 적록색약

---

문제

 

---

오답

n = int(input())
arr= []

for i in range(n):
    arr.append(list(input())
    
def dfs(x,y,color):
    if x<0 or y<0 or x>=n or y>=n :
        return 0
    if  arr[y][x] == color:
        arr[y][x] = 0
        return 1+dfs(x-1,y,color)+dfs(x+1,y,color)+dfs(x,y-1,color)+dfs(x,y+1,color)
    return 0

rgb = [0,0,0]

for idx,value in enumerate('RGB'):
    for i in range(n):
        for j in range(n):
            if arr[i][j] == value:
                dfs(j,i,value)
                rgb[idx] += 1
            
print(sum(rgb),rgb[0]+rgb[2])

R,G,B 군집의 수를 따로따로 세고 적록색약이 없으면 모든 군집 수의 합, 적록색약은 R,B의 합으로 구했는데

G가 R이랑 연결됐을때랑 안됐을 때가 케이스가 달라져서 오답.

 

---

풀이

0. 방향성 생각

군집 개수 세기라서 DFS가 편하다. 각각의 군집을 세주는데 arr을 2번 사용해야한다.

잠시 빈 어레이에 G가 R로 변경된 리스트가 필요하다. 

 

1. 입력받기

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
arr,temp = [],[]

for i in range(n):
    s = input()
    arr.append(list(s))
    s = s.replace('G','R')
    temp.append(list(s))

replace로 기본 입력은 arr로, G를 R로 바꾼 어레이는 temp 리스트에 넣어준다

 

2. DFS 함수 정의

 

def dfs(x,y,color):
    if x<0 or y<0 or x>=n or y>=n :
        return 0
    if  arr[y][x] == color:
        arr[y][x] = 0
        return 1+dfs(x-1,y,color)+dfs(x+1,y,color)+dfs(x,y-1,color)+dfs(x,y+1,color)
    return 0

색깔을 보고 주변 군집까지 카운트하는 경우이므로 color 인자를 받아서 같은색깔만 세기

 

3. 출력

count = [0,0]
for idx,person in enumerate(['RGB','RB']):
    for color in person:
        for i in range(n):
            for j in range(n):
                if arr[i][j] == color:
                    dfs(j,i,color)
                    count[idx] += 1
    if idx == 0:
        arr = temp
        
print(count[0],count[1])

좀 더러워보이지만 4중 for문을 써서 출력

색약이 없는 경우 RGB가 입력으로 들어가고 R,G,B 경우를 세준다. 루프가 끝나면 arr에 저장해놨던 temp 할당

다음 루프는 색약이 있는 경우로 R,B의 경우를 세준다.

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n = int(input())
arr,temp = [],[]

for i in range(n):
    s = input()
    arr.append(list(s))
    s = s.replace('G','R')
    temp.append(list(s))
    
def dfs(x,y,color):
    if x<0 or y<0 or x>=n or y>=n :
        return 0
    if  arr[y][x] == color:
        arr[y][x] = 0
        return 1+dfs(x-1,y,color)+dfs(x+1,y,color)+dfs(x,y-1,color)+dfs(x,y+1,color)
    return 0

count = [0,0]
for idx,person in enumerate(['RGB','RB']):
    for color in person:
        for i in range(n):
            for j in range(n):
                if arr[i][j] == color:
                    dfs(j,i,color)
                    count[idx] += 1
    if idx == 0:
        arr = temp
        
print(count[0],count[1])

 

골드 그래프 문제로 넘어오니까 조건이 하나씩 달리는데 조건 따라서 난이도 편차가 심해지는듯