[알고리즘][Python] 백준 10026 적록색약 문제 풀이

문제 출처 : www.acmicpc.net/problem/10026

10026번: 적록색약

---

문제 해석 : 적록 색약인 사람과 아닌 사람이 보는 그림에서 구역 수의 차이를 구하는 문제이다.

 

문제 풀이 :  전형적인 BFS의 구역 구하기 문제에서 적색과 녹색을 구별하지 못하는 부분이 추가된 문제이다. 이 부분을 새로운 배열을 선언함으로 중복 코딩 없이 해결 할 수 있다.

---

풀이 코드

from collections import deque

def normal(a, b, Arr):

    Q = deque()
    Q.append([a,b])
    visited_n[a][b] = 1

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

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

            if 0 <= nx < N and 0 <= ny < N:
                if visited_n[nx][ny] == 0 and Arr[x][y] == Arr[nx][ny]:
                    Q.append([nx,ny])
                    visited_n[nx][ny] = normal

N = int(input())
arr = [list(input()) for _ in range(N)]
arr2 = [["A"] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if arr[i][j] == "R":
            arr2[i][j] = "G"
        else:
            arr2[i][j] = arr[i][j]

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

normal_n = 0
visited_n = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if visited_n[i][j] == 0:
            normal_n += 1
            normal(i,j,arr)

print(normal_n , end=" ")

normal_n = 0
visited_n = [[0] * N for _ in range(N)]

for i in range(N):
    for j in range(N):
        if visited_n[i][j] == 0:
            normal_n += 1
            normal(i,j,arr2)

print(normal_n)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.