[코딩인터뷰] 백준 10026번

백준 10026번

BFS

from collections import deque

# R G B 적록 색약 시 R = G
n = int(input())
pic = []
for _ in range(n):
    pic.append(list(input()))

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

v_a = [[False] * n for _ in range(n)]
v_b = [[False] * n for _ in range(n)]

c_a = 0
c_b = 0

for i in range(n):
    for j in range(n):
        if not v_a[i][j]:
            rgb_a = pic[i][j]
            q_a = deque()
            q_a.append((i, j))
            v_a[i][j] = True
            c_a += 1

        if not v_b[i][j]:
            rgb_b = pic[i][j]
            q_b = deque()
            q_b.append((i,j))
            v_b[i][j] = True
            c_b += 1

        while 0 < len(q_a) or 0 < len(q_b):

            p_a = 0 < len(q_a)
            p_b = 0 < len(q_b)

            if p_a:
                x_a, y_a = q_a.popleft()

            if p_b:
                x_b, y_b = q_b.popleft()

            for k in range(4):
                if p_a:
                    nx_a = x_a + dx[k]
                    ny_a = y_a + dy[k]

                    if 0 <= nx_a < n and 0 <= ny_a < n:
                        if pic[nx_a][ny_a] == rgb_a and not v_a[nx_a][ny_a]:
                            q_a.append((nx_a, ny_a))
                            v_a[nx_a][ny_a] = True

                if p_b:
                    nx_b = x_b + dx[k]
                    ny_b = y_b + dy[k]

                    if 0 <= nx_b < n and 0 <= ny_b < n:
                        if not v_b[nx_b][ny_b]:
                            if rgb_b == 'B' and pic[nx_b][ny_b] == 'B':
                                q_b.append((nx_b, ny_b))
                                v_b[nx_b][ny_b] = True
                            elif (rgb_b == 'R' or rgb_b == 'G') and pic[nx_b][ny_b] != 'B':
                                q_b.append((nx_b, ny_b))
                                v_b[nx_b][ny_b] = True

print(f"{c_a} {c_b}")

DFS

import sys
sys.setrecursionlimit(100000)

def dfs_a(v, x, y):

    v[x][y] = True
    color = pic[x][y]

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < n and 0 <= ny < n:
            if pic[nx][ny] == color and not v[nx][ny]:
                dfs_a(v, nx, ny)

def dfs_b(v, x, y):

    v[x][y] = True
    color = pic[x][y]

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if 0 <= nx < n and 0 <= ny < n:
            if not v_b[nx][ny]:
                if color == 'B' and pic[nx][ny] == 'B':
                    dfs_b(v, nx, ny)
                elif (color == 'R' or color == 'G') and (pic[nx][ny] == 'R' or pic[nx][ny] == 'G'):
                    dfs_b(v, nx, ny)

n = int(input())
pic = []
for _ in range(n):
    pic.append(list(input()))
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

c_a = 0
c_b = 0

v_a = [[False] * n for _ in range(n)]
v_b = [[False] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        if not v_a[i][j]:
            dfs_a(v_a, i, j)
            c_a += 1
        if not v_b[i][j]:
            dfs_b(v_b, i, j)
            c_b += 1

print(f"{c_a} {c_b}")