Baekjoon 10026번 적록색약

문제

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

걸린 시간

00 : 58 : 37

풀이

Python3

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

# 상하좌우
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

def adj_color(p, r, c):
    q = deque()
    q.append([r, c])
    color = p[r][c]
    p[r][c] = 0
    while q:
        x, y = q.popleft()
        for i in range(0, 4):
            nx = x+dx[i]
            ny = y+dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if p[nx][ny] == color:
                    p[nx][ny] = 0
                    q.append([nx, ny])

def zones(p):
    count = 0
    for r in range(0, N):
        for c in range(0, N):
            # 칸에 색칠이 되어 있으면
            # (0이 아닌 값은 모두 참)
            if p[r][c]:
                count += 1
                adj_color(p, r, c)
    return count

if __name__ == "__main__":
    N = int(input())

    pic = []
    rg_pic = []

    for _ in range(0, N):
        row = list(input().strip())
        rg_row = []

        # 일반 그림
        pic.append(row)

        # 적록색약 그림
        for i in range(0, N):
            if row[i] == 'G':
                rg_row.append('R')
            else:
                rg_row.append(row[i])
        rg_pic.append(rg_row)

    # 연결요소의 개수 찾기
    print(zones(pic), zones(rg_pic))

solved.ad 기준 골드5 문제 치고는 쉬운 편에 속했다.

BFS, DFS 탐색을 이용해 연결 요소의 개수를 찾는 그래프 문제이다.