[파이썬/Python] 백준 10026번: 적록색약

숨·2024년 9월 12일

코테

알고리즘 문제 풀이

목록 보기

72/105

📌 문제 : 백준 10026번

📌 문제 탐색하기

N : 그리드 크기 $(1 ≤ N ≤ 100)$

조건에 따라 적록색약인 사람이 볼 수 있는 구역의 수와 아닌 사람이 볼 수 있는 구역의 수를 구하는 문제이다.

문제 풀이

N×N인 그리드는 각 칸에 R(빨강), G(초록), B(파랑) 중 하나의 색 정보를 담고 있다.

⭐️ 같은 구역 판단 기준

구역 = 같은 색으로 이루어짐.

상하좌우에 같은 색이 인접 → 같은 구역에 속함

적록색약 ⭕️

2가지 색 구분 = R & G + B

적록색약 ❌

3가지 색 구분 = R + G + B

위의 기준에 따라 구역의 수를 얻는 BFS 함수를 구현한다.

BFS 구현하기

현재 위치의 색을 저장하면서 상하좌우에 동일한 색이 있는지 찾는다.

적록색약 ⭕️

R과 G를 동일한 색 취급해 인접하면 같은 구역으로 계산하면 된다.

2가지 경우에 따라 조건을 달리 하여 BFS를 수행할 것이므로, 적록색맹 여부를 의미하는 bool 자료형 변수를 따로 정의해준다.

BFS를 한번 수행하면 하나의 구역을 얻게 된다.

탐색 1회가 끝나면 카운트❗️

N×N의 전체 그리드 중 방문하지 않은 그리드를 탐색하면서, 적록색맹 상태에 따라 BFS를 두번 수행해 얻은 구역의 수를 공백 구분해 출력하면 될 것이다.

가능한 시간복잡도

전체 그리드 탐색하면서 BFS 수행 → $O(N^2)$

최종 시간복잡도
$O(N^2)$ 으로 최악의 경우 $O(10000)$ 이 되어 1초 내에 수행 가능하다.

알고리즘 선택

전체 그리드를 돌면서 BFS를 통해 경우에 따라 같은 색이 있는 구역을 탐색하기

📌 코드 설계하기

BFS 구현
1-1. 현재 색 확인
1-2. 적록색약 여부에 따라 다른 조건으로 같은 색 구역 탐색
필요한 입력 받기
2가지 경우에 대해 BFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys
from collections import deque

input = sys.stdin.readline


# BFS 함수 구현
def bfs(x, y, color):
    queue = deque([(x, y)])
    # 방문 처리
    visited[x][y] = 1
    # 현재 색 확인
    current_color = grid[x][y]

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

        for i in range(4):
            nx, ny = x + directions[i][0], y + directions[i][1]

            if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
                # 적록색맹일 경우
                if color:
                    if current_color in 'RG' and grid[nx][ny] in 'RG':
                        queue.append((nx, ny))
                        visited[nx][ny] = 1
                    elif current_color == 'B' and grid[nx][ny] in 'B':
                        queue.append((nx, ny))
                        visited[nx][ny] = 1

                # 적록색맹 아닐 경우
                else:
                    if grid[nx][ny] == current_color:
                        queue.append((nx, ny))
                        visited[nx][ny] = 1


# 상하좌우 정의
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# N 입력
N = int(input())

# 구역 정보 입력
grid = [list(input().rstrip()) for _ in range(N)]

# 적록색맹인 사람이 봤을 때
visited = [[0] * N for _ in range(N)]
count_1 = 0

for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j, color=False)
            count_1 += 1

# 적록색맹 아닌 사람이 봤을 때
visited = [[0] * N for _ in range(N)]
count_2 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j, color=True)
            count_2 += 1

# 정답 출력
print(count_1, count_2)