BOJ 10026 - 적록색약

문제

백준 온라인 저지 - 10026번

풀이 과정

입력된 board 의 크기가 크지 않으므로 DFS 탐색을 통해 모든 구간을 찾아줬습니다.

색맹이 있는 사람과 없는 사람은 탐색 제약조건이 다르기 때문에 각각 visit 배열을 만들어서 따로 탐색을 수행했습니다.

2번의 DFS 를 수행해도 총 시간 복잡도가 O(2n) 이기 때문에 시간 내에 수행이 가능했습니다.

코드

import sys

sys.setrecursionlimit(10**6)


N = int(input())
board = []
for _ in range(N):
    board.append(list(sys.stdin.readline()[:-1]))

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


def dfs(x, y, visit, decision):
    visit[x][y] = 1

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < N and 0 <= ny < N:
            if not visit[nx][ny] and board[nx][ny] in decision:
                dfs(nx, ny, visit, decision)


def solution():
    normal_visit = [[0]*N for _ in range(N)]
    sick_visit = [[0]*N for _ in range(N)]

    ans = [0, 0]
    for r in range(N):
        for c in range(N):
            if not normal_visit[r][c]:
                dfs(r, c, normal_visit, [board[r][c]])
                ans[0] += 1
            if not sick_visit[r][c]:
                if board[r][c] == 'R' or board[r][c] == 'G':
                    dfs(r, c, sick_visit, ['R', 'G'])
                else:
                    dfs(r, c, sick_visit, ['B'])
                ans[1] += 1

    return ' '.join(map(str, ans))


print(solution())