백준 > 적록색약

❓ 문제

백준 골드5 문제 > 적록색약

❗ 해결

BFS로 풀었다.

먼저 적록색약이 아닌 사람부터 구하고, 그다음 적록색약인 사람을 구했다.

n = int(input())
board = []

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

dic = {'R': 1, 'G': 2, 'B': 3}

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

normal_count = 0
red_green_blind_count = 0

for _ in range(n):
    s = str(input())
    temp_list = []
    for char in s:
        temp_list.append(dic[char])

    board.append(temp_list)

나는 보기 편하게 그냥 숫자로 바꿔줬는데, 그냥 문자열을 숫자로 안바꾸고 풀어도 된다.
내가 한게 비효율적인듯.. 그래도 숫자가 보기 편해서 숫자로 바꿔서 풀었다.

# 적록색약이 아닌 사람
for color in range(1, 4):
    # 1번부터 시작 한다.
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                normal_count += 1

그리고 적록색약이 아닌 사람부터 시작한다.
적록색약이 아닌 사람은 RGB를 다 볼수 있으니, 바깥쪽 반복문에서 1,2,3 순서대로 구한다.

def bfs(x, y, color):

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

    queue = deque()
    queue.append([x, y])
    visited[x][y] = 1

    while queue:

        x, y = queue.popleft()

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

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and board[nx][ny] == color:
                visited[nx][ny] = 1
                queue.append([nx, ny])

bfs 함수이다.
현재 색상을 파라미터로 넘겨줘서 해당 색상만 찾도록 조건을 걸었다.

# 적록색약인 사람
# 방문한 곳을 체크하는 리스트를 초기화해줌.
visited = [[0] * n for _ in range(n)]

# G(2)면 R(1)로 전부 통일 한다.
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 1

for color in [1, 3]:
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                red_green_blind_count += 1

print(normal_count, red_green_blind_count)

다 찾았으면 적록색약인 사람이 봤을 때 나오는 구역의 수를 구한다.
이때 방문한 곳을 체크하는 리스트는 다시 0으로 초기화를 해주고,
적록색약인 사람은 R,G를 구분하지 못하므로 G를 R로 바꿔주었다 ( 2-> 1 )

그리고 똑같이 bfs 함수를 실행한다.

전체코드

from collections import deque

def bfs(x, y, color):

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

    queue = deque()
    queue.append([x, y])
    visited[x][y] = 1

    while queue:

        x, y = queue.popleft()

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

            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny] == 0 and board[nx][ny] == color:
                visited[nx][ny] = 1
                queue.append([nx, ny])


n = int(input())
board = []

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

dic = {'R': 1, 'G': 2, 'B': 3}


normal_count = 0
red_green_blind_count = 0

for _ in range(n):
    s = str(input())
    temp_list = []
    for char in s:
        temp_list.append(dic[char])

    board.append(temp_list)

# 적록색약이 아닌 사람
for color in range(1, 4):
    # 1번부터 시작 한다.
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                normal_count += 1

# 적록색약인 사람
# 방문한 곳을 체크하는 리스트를 초기화해줌.
visited = [[0] * n for _ in range(n)]

# G(2)면 R(1)로 전부 통일 한다.
for i in range(n):
    for j in range(n):
        if board[i][j] == 2:
            board[i][j] = 1

for color in [1, 3]:
    for i in range(n):
        for j in range(n):
            if visited[i][j] == 0 and board[i][j] == color:
                bfs(i, j, color)
                red_green_blind_count += 1

print(normal_count, red_green_blind_count)