[백준 / 10026] 적록색약

in Problem Solving on BaekJoon


날짜: 2021년 10월 4일
소요 시간: 1시간 5분 12초
카테고리: 그래프 탐색
태그: gold.5, 10026, 파이썬

백준 10026 - 적록색약

입출력 예시

예제 입력예제 출력
54 3
RRRBB 
GGBBB 
BBBRR 
BBRRR 
RRRRR 

내가 적은 코드

import sys
sys.setrecursionlimit(10**6)

# 빨강 탐색
def dfs_R(a, b, graph):
    if a < 0 or a >= N or b < 0 or b >= N or graph[a][b] == 0 or graph[a][b] != 'R':
        return

    graph[a][b] = 0

    dfs_R(a + 1, b, graph)
    dfs_R(a - 1, b, graph)
    dfs_R(a, b + 1, graph)
    dfs_R(a, b - 1, graph)

# 초록 탐색
def dfs_G(a, b, graph):
    if a < 0 or a >= N or b < 0 or b >= N or graph[a][b] == 0 or graph[a][b] != 'G':
        return

    graph[a][b] = 0

    dfs_G(a + 1, b, graph)
    dfs_G(a - 1, b, graph)
    dfs_G(a, b + 1, graph)
    dfs_G(a, b - 1, graph)

# 파랑 탐색
def dfs_B(a, b, graph):
    if a < 0 or a >= N or b < 0 or b >= N or graph[a][b] == 0 or graph[a][b] != 'B':
        return

    graph[a][b] = 0

    dfs_B(a + 1, b, graph)
    dfs_B(a - 1, b, graph)
    dfs_B(a, b + 1, graph)
    dfs_B(a, b - 1, graph)


N = int(sys.stdin.readline())
graph1 = list()
graph2 = list()

# 그래프 입력 graph1 -> 정상인 / graph -> 적록색약
for _ in range(N):
    graph1.append([])
    graph2.append([])

for i in range(N):
    for j in list(sys.stdin.readline().rstrip()):
        graph1[i].append(j)
        if j == 'G':
            graph2[i].append('R')
        else:
            graph2[i].append(j)

count1 = 0
count2 = 0

# 정상인일 때 색 배열 확인
for k in range(N):
    for l in range(N):
        if graph1[k][l] != 0:
            if graph1[k][l] == 'R':
                dfs_R(k, l, graph1)
                count1 += 1
            elif graph1[k][l] == 'G':
                dfs_G(k, l, graph1)
                count1 += 1
            elif graph1[k][l] == 'B':
                dfs_B(k, l, graph1)
                count1 += 1

# 적록색약일 때 색 배열 확인
for m in range(N):
    for n in range(N):
        if graph2[m][n] != 0:
            if graph2[m][n] == 'R':
                dfs_R(m, n, graph2)
                count2 += 1
            elif graph2[m][n] == 'B':
                dfs_B(m, n, graph2)
                count2 += 1

print(count1, count2)

풀이 과정

얼마 전 풀었던 백준 1012 - 유기농 배추와 leetcode -Number of Islands 같은 재귀형태의 DFS 유형
(물론 BFS나 반복형태의 DFS로 풀 수 있을거다... 아마…)

달랐던 점은 1과 0의 흑백으로 나눌 수 있었던 체크형태에서 RGB라는 세가지 선택지가 생겼다는 점

시간을 효율적으로 사용할 수 있는 하나의 함수에 세가지를 모두 체크할 수 있는 함수를 짤 수 있을지를 한참을 고민하다가 그냥 세가지 경우의 수를 모두 체크하게끔 함수를 세개를 만듦
(다행히 시간이나 메모리 초과가 나지않은 것으로 보아 이렇게 풀어도 되는 것 같다.)

이것 외에는 이전의 문제와 풀이가 같으므로 크게 설명할 것이 없을 것 같음

베스트 코드

import sys
sys.setrecursionlimit(10**5)
n=int(input())
a=[[" "]*(n+2)]+[list(" "+input()+" ")for i in[0]*n]+[[" "]*(n+2)]
b=[i.copy()for i in a]
def cnt(s,x,y,c):
    s[x][y]=" "
    if s[x-1][y]==c:cnt(s,x-1,y,c)
    if s[x+1][y]==c:cnt(s,x+1,y,c)
    if s[x][y-1]==c:cnt(s,x,y-1,c)
    if s[x][y+1]==c:cnt(s,x,y+1,c)
c=d=0
for i in range(1,n+1):
    for j in range(1,n+1):
        if a[i][j]!=" ":
            cnt(a,i,j,a[i][j]);c+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        if b[i][j]=="G":b[i][j]="R"
for i in range(1,n+1):
    for j in range(1,n+1):
        if b[i][j]!=" ":
            cnt(b,i,j,b[i][j]);d+=1
print(c,d)

반성

  • 세가지 함수를 정의한 나와는 달리 하나의 함수만 정의 했지만 색을 나타내는 파라미터 하나를 추가해서 하나로 함수를 정의하였다.
  • 시간은 조금 더 효율적으로 사용할 수 있지만 큰 로직으로 봤을 때 베스트코드도 나와 같은 로직으로 풀었다고 볼 수 있다.


© 2021. by hminkim