문제

골드5

R,G,B 각각 그룹의 개수를 구하기 / 그런데 R==G 인 경우의 그룹 개수도 또 따로 구합시다

아이디어

위에 적힌 그대로이다. 아파트 동 개수 이런거 dfs로 풀었던 생각이 나서 dfs로 풀었는데, 재귀 개수 초과가 떳다. dfs로 풀 수 있으면 bfs로 풀 수 있겠는데? 라는 생각이 들어서, bfs로 풀었다.

코드

import sys
from collections import deque
sys.stdin=open('BOJ10026.txt')
dr = [1, -1, 0, 0]
dc = [0, 0, 1, -1]

def bfs(c, r):
    q.append([c, r])
    visit[c][r] = 1
    while q:
        c, r = q.popleft()
        for i in range(4):
            nc = c + dc[i]
            nr = r + dr[i]
            if 0 <= nc < n and 0 <= nr < n:
                if arr[nc][nr] == arr[c][r] and visit[nc][nr] == 0:
                    q.append([nc, nr])
                    visit[nc][nr] = 1

n = int(input())
arr = [list(map(str, input())) for _ in range(n)]
visit = [[0]*n for _ in range(n)]
q = deque()

cnt = 0
for c in range(n):
    for r in range(n):
        if visit[c][r] == 0:
            bfs(c, r)
            cnt += 1
print(cnt, end=' ')

for c in range(n):
    for r in range(n):
        if arr[c][r] == 'R':
            arr[c][r] = 'G'
visit = [[0]*n for _ in range(n)]

cnt = 0
for c in range(n):
    for r in range(n):
        if visit[c][r] == 0:
            bfs(c, r)
            cnt += 1
print(cnt)