백준 10026번: 적록색약 [골드5] - Python

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

10026번: 적록색약

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

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

알고리즘 분류

그래프 이론, 그래프 탐색, DFS, BFS

 

풀이

단순한 DFS, BFS문제보다 한걸음 더 나아간 문제라고 볼 수 있겠습니다. 실버1~2 난이도 문제 중에 DFS/BFS 문제가 많은데, 이 문제는 골드 5라서 그런지 아주 살짝 더 복잡하군요! 이 문제는 다음과 같이 풀 수 있겠습니다.

 

1. 적록색약이 아닌 사람과 적록색약인 사람이 보는 그림을 따로 2차원 리스트로 생성한다. 적록색약인 사람의 그림은 아닌 사람의 그림에서 'G'를 'R'로 바꿔주는 것으로 생성한다.
2. 두 그림을 따로 DFS한다.

사실 1번 절차가 추가된 것 말고는 전형적인 DFS/BFS문제라고 할 수 있겠네요. 물론 저는 여기서도 문제를 겪었습니다. '두 그림을 따로 DFS 한다면 DFS함수를 2개를 정의해서, 각각 따로 함수에 넣어주어야 하나?'

그렇게 해서 작성한 것이 아래 코드입니다. 

import copy
import sys
sys.setrecursionlimit(15000)
input = sys.stdin.readline

n = int(input())

pict = []
for i in range(n):
    pict.append(list(input().strip()))

m = len(pict[0])

#적록색약이 보는 그림
pictSY = copy.deepcopy(pict)
for i in range(n):
    for j in range(m):
        if pictSY[i][j] == 'G':
            pictSY[i][j] = 'R'

#일반인용 DFS
def dfsNotSY(r, c, color):
    if r < 0 or r >= n or c < 0 or c >= n:
        return
    if pict[r][c] == 'V' or pict[r][c] != color:
        return

    pict[r][c] = 'V'
    dfsNotSY(r - 1, c, color)
    dfsNotSY(r + 1, c, color)
    dfsNotSY(r, c - 1, color)
    dfsNotSY(r, c + 1, color)

    return True

#적록색약용 DFS
def dfsSY(r, c, color):
    if r < 0 or r >= n or c < 0 or c >= n:
        return
    if pictSY[r][c] == 'V' or pictSY[r][c] != color:
        return

    pictSY[r][c] = 'V'
    dfsSY(r - 1, c, color)
    dfsSY(r + 1, c, color)
    dfsSY(r, c - 1, color)
    dfsSY(r, c + 1, color)
    return True


#일반인 DFS 실행
cntNotSY = 0
for i in range(n):
    for j in range(m):
        if dfsNotSY(i, j, pict[i][j]) == True:
            cntNotSY += 1

#적록색약인 DFS 실행
cntSY = 0
for i in range(n):
    for j in range(m):
        if dfsSY(i, j, pictSY[i][j]) == True:
            cntSY += 1

print(cntNotSY, cntSY)

여기서 잠깐! pict를 pictSY로 복사하려면 picSY = pict를 하면 될까요? 이렇게 하면 pict와 pictSY라는 객체가 같은 리스트를 가리키게 됩니다. 따라서 pictSY를 수정하면 pict에서도 수정되는 문제가 발생하죠.. 이를 해결하기 위해서 copy모듈의 deepcopy() 메서드를 사용한 것입니다.

 

물론 이렇게 작성해도 정답처리를 받았습니다만.. 너무 지저분하고 가독성이 떨어지는 게 아니겠습니까?! 그래서 함수 하나만 가지고도 이 문제를 풀 수 있으면 좋겠다.. 이렇게 생각했는데 역시 함수 하나만으로 푼 분이 계시더군요!

DFS를 할 때, 저는 그림의 픽셀을 'V'로 바꾸는 것으로 방문처리를 했는데, 그렇게 하지 말고 방문했는지의 정보를 담고 있는 `visited` 리스트를 정의하고 이 `visited`를 통해 방문처리를 하는 것이 핵심이었습니다. 그렇게 해서 코드를 새로 작성해 보았습니다.

#개선된 코드

import copy
import sys
sys.setrecursionlimit(15000)
input = sys.stdin.readline

n = int(input())


def dfs(r, c, color):
    if r < 0 or r >= n or c < 0 or c >= n:
        return
    if pict[r][c] != color:
        return
    if visited[r][c] == 1:
        return

    #방문처리
    visited[r][c] = 1

    dfs(r - 1, c, color)
    dfs(r + 1, c, color)
    dfs(r, c - 1, color)
    dfs(r, c + 1, color)
    return


#일반인 DFS
cntNotSY = 0
pict = []
for i in range(n):
    pict.append(list(input().strip()))
visited = [[0]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            dfs(i, j, pict[i][j])
            cntNotSY += 1

#적록색약 DFS
cntSY = 0
for i in range(n):
    for j in range(n):
        if pict[i][j] == 'G':
            pict[i][j] = 'R'
visited = [[0]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if visited[i][j] == 0:
            dfs(i, j, pict[i][j])
            cntSY += 1

print(cntNotSY, cntSY)

함수를 한 번만 정의하고도 정답을 출력할 수 있었습니다. 그리고 여기서 하나 더 바뀐 점이 있는데요, dfs함수의 리턴값이 True인지(DFS가 완료되었는지)를 판단해 카운트를 +1 하는 방식에서 픽셀이 방문되었는지(DFS가 아직 수행되지 않았는지)를 판단해 카운트를 +1하는 방식으로 바꿔봤습니다. 이런 방식도 있더라구요. 개인적으로는 이 방식이 더 직관적인 것 같아서 앞으로는 이 방식으로 코딩해야겠습니다~!