[백준 10026] 파이썬 - 적록색 약

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

10026번: 적록색약

 

 

# 조건

• 적록색약은 빨간색과 초록색의 차이 거의 x
• 크기가 NxN인 그리드의 각 칸에 R, G , B 중 하나를 색칠한 그림
• 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색
• 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역

 

• 위의 경우 - 적록색약이 아닌 사람이 보면 구역의 수 총 4개 ( 빨 2, 초1, 파 1)
• 적록색 약인 경우 3개 (빨-초 2개, 파 1개)
• 그림이 주어질 때, 적록색약이 아닌 사람이 봤을 때와 맞는 사람이 봤을 때 구역의 수를 구하라

 

# 접근 방법

• BFS를 이용하여 주변이 같은 색깔인 경우를 체크 해주며 +1을 해준다.
• 반복문 내에서 순회를 하며 새로운 리스트에 방문 표시를 하여 중복된 구역 체크 안하도록 해준다.
• 적록색 약이 아닌 경우부터 체크 !

 

당연히 시간초과;;

import sys  
sys.stdin = open('input.txt')  
from collections import deque  
input = sys.stdin.readline  
  
  
# 델타함수  
di, dj = [-1,1,0,0],[0,0,1,-1]  
def check1(color, start):  
    global visited, di, dj, grid  
    q = deque()  
    q.append(start)  
    while q:  
        sti, stj = q.popleft()  
        visited[sti][stj] = 1  
        for k in range(4):  
            ni, nj = sti + di[k], stj + dj[k]  
            if 0<=ni<n and 0<=nj<n and grid[ni][nj] == color and visited[ni][nj] == 0:  
                q.append((ni,nj))  
  
def check2(color, start):  
    global visited2, di, dj, grid  
    q = deque()  
    q.append(start)  
    while q:  
        sti, stj = q.popleft()  
        visited2[sti][stj] = 1  
        for k in range(4):  
            ni, nj = sti + di[k], stj + dj[k]  
            if color == 'R' or color == 'G':  
                if 0<=ni<n and 0<=nj<n and (grid[ni][nj] == 'R' or grid[ni][nj] == 'G') and visited2[ni][nj] == 0:  
                    q.append((ni,nj))  
            else:  
                if 0<=ni<n and 0<=nj<n and grid[ni][nj] == color and visited2[ni][nj] == 0:  
                    q.append((ni,nj))  
  
  
n = int(input())  
grid = [list(input().rstrip()) for _ in range(n)]  
  
# 반복문 순회 하면서 체크해주기  
# 적록색 약이 아닌 경우  
#방문 표시 남겨주기  
visited = [[0]*n for _ in range(n)]  
cnt1 = 0  
cnt2 = 0  
for i in range(n):  
    for j in range(n):  
        # 방문 표시 남겨주기  
        color = grid[i][j]  
        if visited[i][j] == 0:  
            check1(color, (i,j))  
            cnt1 +=1  
print(cnt1)  
  
#방문 표시 남겨주기  
visited2 = [[0]*n for _ in range(n)]  
cnt = 0  
for i in range(n):  
    for j in range(n):  
        # 방문 표시 남겨주기  
        color = grid[i][j]  
        if visited2[i][j] == 0:  
            check2(color, (i,j))  
            cnt2 +=1  
  
print(cnt2)

• 당연한 건줄 알았는데 아니였다..
• visited에 방문기록을 남겨줄 때, ni, nj의 유효성 검사를 해준 후 바로 기록을 남겨주니 통과가 되었다.
• 오랜만의 bfs라 헷갈렸는 듯..

import sys
from collections import deque
input = sys.stdin.readline

di, dj = [-1, 1, 0, 0], [0, 0, 1, -1]


def check1(color, start):
    global visited, di, dj, grid
    q = deque()
    q.append(start)
    while q:
        sti, stj = q.popleft()

        for k in range(4):
            ni, nj = sti + di[k], stj + dj[k]
            if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == color and visited[ni][nj] == 0:
                q.append((ni, nj))
                visited[ni][nj] = 1


def check2(color, start):
    global visited2, di, dj, grid
    q = deque()
    q.append(start)
    while q:
        sti, stj = q.popleft()

        for k in range(4):
            ni, nj = sti + di[k], stj + dj[k]
            if color == 'R' or color == 'G':
                if 0 <= ni < n and 0 <= nj < n and (grid[ni][nj] == 'R' or grid[ni][nj] == 'G') and visited2[ni][
                    nj] == 0:
                    q.append((ni, nj))
                    visited2[ni][nj] = 1

            else:
                if 0 <= ni < n and 0 <= nj < n and grid[ni][nj] == color and visited2[ni][nj] == 0:
                    q.append((ni, nj))
                    visited2[ni][nj] = 1


n = int(input())
grid = [list(input().rstrip()) for _ in range(n)]

# 반복문 순회 하면서 체크해주기
# 적록색 약이 아닌 경우
# 방문 표시 남겨주기
visited = [[0] * n for _ in range(n)]
cnt1 = 0
cnt2 = 0
for i in range(n):
    for j in range(n):
        # 방문 표시 남겨주기
        color = grid[i][j]
        if visited[i][j] == 0:
            visited[i][j] = 1
            check1(color, (i, j))
            cnt1 += 1
print(cnt1, end=' ')

# 방문 표시 남겨주기
visited2 = [[0] * n for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        # 방문 표시 남겨주기
        color = grid[i][j]
        if visited2[i][j] == 0:
            visited2[i][j] = 1
            check2(color, (i, j))
            cnt2 += 1

print(cnt2)