백준 - 10026

문제 설명

색으로 구역을 의미하는 R G B로 이루어진 n * n의 크기의 지역에서 적색과 녹색을 구분하지 못하는 적록색약과 일반인에서의 구역 수를 구하는 프로그램이다.

접근 방법

• bfs를 활용해 모든 위치를 방문하며, 같은 색깔이면서 아직 방문하지 않은 곳을 모두 탐색
• 2중 for문을 사용해 탐색 수행, 탐색이 끝날 때 마다 영역 수 1 증가하는 방식으로 작성
• 색약의 경우에는, 초록을 의미하는 G를 R로 치환하여 동일한 과정 반복 수행

작성한 코드

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())

def bfs(x, y, area):
    queue.append((x, y))
    
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    
    visit[x][y] = 1

    while queue:
        x, y = queue.popleft()

        for j in range(4):
            ax = x + dx[j]
            ay = y + dy[j]

            if 0 <= ax < n and 0 <= ay < n and area[ax][ay] == area[x][y] and not visit[ax][ay]:
                 visit[ax][ay] = 1
                 queue.append((ax, ay))

map = []
map_v2 = []

for i in range(n):
    line = input().rstrip()
    map.append(list(line))
    map_v2.append(list(line.replace("G", "R")))

queue = deque()

# 일반인

visit = [[0] * n for _ in range(n)]
count1 = 0

for i in range(n):
    for k in range(n):
        if not visit[i][k]:
            bfs(i, k, map)
            count1 += 1

# 적록색약
visit = [[0] * n for _ in range(n)]
count2 = 0

for i in range(n):
    for k in range(n):
        if not visit[i][k]:
            bfs(i, k, map_v2)
            count2 += 1

print(count1, count2)