백준 10026 적록색약 (파이썬)

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

문제

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

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

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

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

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

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

입력

 

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

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

출력

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

첫번째 코드 (정답)

import sys
from collections import deque
from collections import defaultdict
def BFS(i, j, visited, dic):
    q = deque([])
    q.append([i, j])
    colors = [0]*3
    if arr[i][j] == "R":
        dic["R"] += 1
    elif arr[i][j] == "G":
        dic["R"] += 1
    else:
        dic["B"] += 1

    while q:
        x, y = q.popleft()
        for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
            nx, ny = x + dx, y + dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if visited[nx][ny]:
                continue
            if arr[x][y] == arr[nx][ny]:
                visited[nx][ny] = 1
                q.append([nx, ny])
    return dic


if __name__=="__main__":
    input = sys.stdin.readline
    n = int(input().strip())
    arr = []
    for i in range(n):
        string = list(input().strip())
        temp = []
        for s in string:
            temp.append(s)
        arr.append(temp)
    n = len(arr)
    m = len(arr[0])
    visited = [[0] * m for _ in range(n)]
    colors = defaultdict(list)
    #leak = defaultdict(list)
    colors["R"] = 0
    colors["G"] = 0
    colors["B"] = 0
    normal = 0
    leak = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j]:
                continue
            visited[i][j] = 0
            colors = BFS(i, j, visited, colors)
    normal = sum(colors.values())

    for i in range(n):
        for j in range(m):
            if arr[i][j] == "G":
                arr[i][j] = "R"

    colors["R"] = 0
    colors["G"] = 0
    colors["B"] = 0
    visited = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if visited[i][j]:
                continue
            visited[i][j] = 0
            colors = BFS(i, j, visited, colors)
    leak = sum(colors.values())
    print(normal, leak)

맞긴 했지만 코드가 너무 길고 깔끔하지 않은 것 같습니다.

먼저 문자열 정보를 배열로 바꾸는 과정에서 불필요한 연산을 했습니다.

리스트가 아니면 참조를 못한다고 생각했는데 

저는 BFS를 두 번 했는데 한번은 RGB를 변경하지 않고 한번은 G를 R로 변경해서 풀었습니다.

그래서 불필요한 연산을 반복했습니다.  

두번째 코드 (정답)

import sys
from collections import deque
def BFS(sick):
    visited = [[0] * m for _ in range(n)]
    cnt = 0
    for i in range(n):
        for j in range(m):
            if visited[i][j]:
                continue
            q = deque([])
            q.append([i, j])
            cnt += 1
            if sick and arr[i][j] != "B":
                colors = "RG"
            else:
                colors = arr[i][j]
            while q:
                x, y = q.popleft()
                for dx, dy in (0, 1), (0, -1), (1, 0), (-1, 0):
                    nx, ny = x + dx, y + dy
                    if nx < 0 or nx >= n or ny < 0 or ny >= m:
                        continue
                    if visited[nx][ny]:
                        continue
                    if arr[nx][ny] in colors:
                        visited[nx][ny] = 1
                        q.append([nx, ny])
    return cnt

if __name__=="__main__":
    input = sys.stdin.readline
    n = int(input().strip())
    arr = [input().strip() for i in range(n)]
    n = len(arr)
    m = len(arr[0])
    normal = BFS(False)
    leak = BFS(True)
    print(normal, leak)

제가 참고한 풀이는 백준 jh05013 님의 코드 입니다.

 

먼저 색약이 있으면서 찾는 구역의 시작이 'B'가 아닌 경우 color를 'RG' 모두를 넣어 BFS하는 동안 R이나 G가 나오는 경우를 커버했습니다.

또한 색약인 경우와 아닌 경우를 bool 값을 넣어 구별하였습니다.