10026번 적록색약

골드 V

💡문제 분석 요약

BFS

💡알고리즘 설계

우선 B는 무조건 세야하는 파트이므로, B를 찾을때 B의 구역을 찾아 숫자를 알 수 있게 find함수에서 실행한다.

방문하지 않은 구역이 없도록 find함수에는 방문하지 않은게 있다면 queue에 넣고 True를 반환한다.

💡코드

더 효율적인 방법으론, G를 찾았을때 R로 변환시켜준다.

import sys
from collections import deque
def find(width):
    global blue
    for i in range(width):
        for j in range(width):
            if not visited[i][j]:
                if rgb[i][j]=='B':
                    blue +=1
                queue.append([i,j])
                return True
                

def find_rg(width):
    for i in range(width):
        for j in range(width):
            if not visited[i][j]:
                if rgb[i][j]!='B':
                    queue.append([i,j])
                    return True
                

dx = [0,0,1,-1]
dy = [1,-1,0,0]

n = int(input())
global rgb
rgb = []
blue = 0
for i in range(n):
    rgb.append(list(map(str,input().strip())))

visited =[ [False for _ in range(n)] for _ in range(n)]
all_answer = []
answer =0
queue = deque()
while find(n):
    while queue:
        x,y= queue.popleft()
        visited[x][y] = True
        for i in range(4):
            x1 = x+ dx[i]
            y1 = y+ dy[i]
            if 0<=x1<n and 0<=y1<n:
                if rgb[x][y]==rgb[x1][y1] and not visited[x1][y1] :
                    queue.append([x1,y1])
                    visited[x1][y1] = True
    
    answer +=1
all_answer.append(answer)
answer = 0

visited =[ [False for _ in range(n)] for _ in range(n)]

not_normal = 0

    
queue = deque()
while find_rg(n):
    while queue:
        x,y= queue.popleft()
        visited[x][y] = True
        for i in range(4):
            x1 = x+ dx[i]
            y1 = y+ dy[i]
            if 0<=x1<n and 0<=y1<n:
                original = rgb[x][y]
                other = rgb[x1][y1]
                if not visited[x1][y1] and  original != 'B' and other !='B':
                    queue.append([x1,y1])
                    visited[x1][y1] = True
    
    not_normal +=1
all_answer.append(not_normal+blue)

print(*all_answer)

💡틀린 이유

• 구역으로 나누는게 분할정복인가 해서 애매했음
• 분할정복이 아닌 이유→ 큰 문제를 작은 문제로 쪼개는 문제가 애초부터 아님.
• 결국 각 구역이 무슨 색인지 탐색을 해야하고, 이를 빨리 하기 위한 방법을 써야함.

💡 기억할 것

• divide conque= 큰 문제를 작은 문제로 쪼개고, 쪼갠 것을 다시 더하면서 값을 계산하는 방식.

• BFS= 결국 탐색이고 어떻게 효율적으로 탐색하냐이다.

  ##