[백준] 10026 파이썬(python) : 적록색약 - (★)

10026번: 적록색약

 

 

dfs풀이 - python3로 제출

import sys
sys.setrecursionlimit(10**5)
n = int(sys.stdin.readline())
graph = [ list(sys.stdin.readline()) for _ in range(n) ]
visit = [[False]*n for _ in range(n) ]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]

RGB_color, GGB_color = 0, 0

def dfs(x, y):
    visit[x][y] = True
    now_color = graph[x][y] #1
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if not visit[nx][ny]:
                if graph[nx][ny] == now_color: #2
                    dfs(nx, ny)

for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            dfs(i, j)
            RGB_color += 1 #3

for i in range(n):
    for j in range(n):
        if graph[i][j] == 'R': #4
            graph[i][j] = 'G'
visit = [ [False]*n for _ in range(n) ] #5

for i in range(n):
    for j in range(n):
        if not visit[i][j]:
            dfs(i, j)
            GGB_color += 1 #6
print(RGB_color, GGB_color)

 

#1 : 처음 순환을 돌때 자신의 color를 기억하기 위한 변수

#2 : 새로운 노드의 값과 저장한 color가 같다면 재귀호출

#3 : 순환을 다 끝내면 색깔별로 color 하나씩 추가

#4 : 적녹색약을 세어주기 위해 graph의 'R'을 모두 'G'로 변경

#5 : RGB_color 세어줄때 방문표시했던것 False로 초기화

#6 : 위와 같은 방법으로 GGB_color 숫자 세어줌

 

기존에 풀던 문제에서 조건이 추가된 문제였다. 세어줘야 하는 그룹이 True인지 False인지만 구분하면 되었지만 이번엔 'R', 'G', 'B' 3가지 그룹이어서 now_color 변수를 만들어주는 것이 인상깊었다. 그리고 2그룹을 묶어서 하나로 세는 방법도 새로 배울 수 있었다.

 

bfs풀이 23.01.14(토) - pypy로 제출

import sys
from collections import deque
n = int(sys.stdin.readline())
graph = [ list(sys.stdin.readline().strip()) for _ in range(n) ]
visit = [ [False] * (n) for _ in range(n) ]
dx = [ 0, 0, -1, 1 ]
dy = [ -1, 1, 0, 0 ]
def bfs(x, y, color):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and visit[nx][ny] == False:
                if graph[nx][ny] == color:
                    visit[nx][ny] = True
                    q.append((nx,ny))
count_RGB = 0
for i in range(n):
    for j in range(n):
        if visit[i][j] == False and graph[i][j] == "R":
            visit[i][j] = True
            bfs(i, j, graph[i][j])
            count_RGB += 1
        if visit[i][j] == False and graph[i][j] == "G":
            visit[i][j] = True
            bfs(i, j, graph[i][j])
            count_RGB += 1
        if visit[i][j] == False and graph[i][j] == "B":
            visit[i][j] = True
            bfs(i, j, graph[i][j])
            count_RGB += 1
count_RRB = 0
visit = [ [False] * n for _ in range(n) ]
for i in range(n):
    for j in range(n):
        if graph[i][j] == "G":
            graph[i][j] = "R"

for i in range(n):
    for j in range(n):
        if visit[i][j] == False:
            if graph[i][j] == "R":
                visit[i][j] = True
                bfs(i, j, graph[i][j])
                count_RRB += 1
        if visit[i][j] == False and graph[i][j] == "B":
            visit[i][j] = True
            bfs(i, j, graph[i][j])
            count_RRB += 1
print(count_RGB, count_RRB)