[PS - Baekjoon] 10026번 적록색약

안녕하세요 배트맨🦇 입니다 !

오늘은 "BOJ 10026번 - 적록색약" 문제를 풀어보았습니다.

그럼 풀이 시작해보겠습니다!

---

10026 : 적록색약

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

10026번: 적록색약

오늘의 문제는 골드5 티어의 문제입니다. BFS 알고리즘을 활용하는 문제입니다.

시간제한과 N의 범위를 보고 시간은 충분하겠다고 생각했습니다.

 

---

다른 문제에 비해 메모가 아주 짧습니다 !

색약일 경우 R과 G를 하나로 보는 방법에 대해 잠깐 고민하다가 

색약이 아닐 경우와 색약일 경우 각각 탐색을 해도 시간이 넉넉할 것 같아서 일단 진행했습니다.

바로 코드로 보겠습니다.

---

Solution

import sys
from collections import deque

def bfs(x, y):
    queue = deque([[x,y]])
    visited[x][y] = True

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

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

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]: 
                if board[nx][ny] == board[x][y]:
                    queue.append([nx, ny])
                    visited[nx][ny] = True

BFS 함수입니다. 앞서 말씀드렸듯이 색약인 경우와 아닌 경우를 main에서 나눠서 진행하기 때문에

BFS 함수에는 다른 장치가 필요 없습니다.

(너무 익숙한 BFS코드ㅠㅠ)

read = sys.stdin.readline
n = int(read())

board = [list(read()) for _ in range(n)]
visited = [[False]*n for _ in range(n)] 
res = [0, 0]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

n과 board를 입력받고, 탐색에 쓰일 2차원 리스트인 visited 와  dx, dy 리스트를 선언합니다.

res는 출력할 변수를 담는 리스트입니다.

for i in range(n): # 색약이 아닌 경우
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            res[0] += 1

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

# 적록색약인 경우
for i in range(n): 
    for j in range(n):
        if board[i][j] == 'G':
            board[i][j] = 'R'

for i in range(n):
    for j in range(n):        
        if not visited[i][j]:
            bfs(i, j)
            res[1] += 1

print(res[0], res[1])

main 코드입니다.

색약이 아닌 경우에 구역을 count 하고, board에 존재하는 G를 모두 R로 바꿔줍니다.

색약인 경우에 다시 한번 구역 count를 합니다.

(G를 R이 아닌 B로 바꾸는 실수 했다가, 한 번 틀렸다,,)

아래는 전체 코드입니다.

import sys
from collections import deque

def bfs(x, y):
    queue = deque([[x,y]])
    visited[x][y] = True

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

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

            if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny]: 
                if board[nx][ny] == board[x][y]:
                    queue.append([nx, ny])
                    visited[nx][ny] = True
    
read = sys.stdin.readline
n = int(read())

board = [list(read()) for _ in range(n)]
visited = [[False]*n for _ in range(n)] 
res = [0, 0]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i, j)
            res[0] += 1

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

for i in range(n):
    for j in range(n):
        if board[i][j] == 'G':
            board[i][j] = 'R'

for i in range(n):
    for j in range(n):        
        if not visited[i][j]:
            bfs(i, j)
            res[1] += 1

print(res[0], res[1])

---

결과

(R이랑 B구분 못해서 틀린 거면 내가 색약 아니냐고...ㅠ)