[백준 10026번] 적록색약 문제 풀이 (with Python)

 

< 문제 >

 

 

 

< 입출력 >

 

 

 

< 풀이 >

방문하지 않은 구역의 인덱스인 경우, 큐에 넣어준다.

큐의 상하좌우를 순서대로 들러, 방문 하지 않은 구역이면서, 해당 배열의 값과 같은 값인 경우, 큐에 새로운 값을 넣어주고, 해당 배열의 방문 여부를 True로 바꿔준다.

N * N 배열을 순서대로 dfs를 돌려, 개수를 세어 출력한다.

 

 

 

< 코드 >

from collections import deque

def dfs(x, y):
    q.append((x, y))
    checked[x][y] = True
    while q:
        x, y = q.popleft()
        checked[x][y] = True
        for i in range(4):
            new_x = x + dx[i]
            new_y = y + dy[i]
            if 0 <= new_x < N and 0 <= new_y < N:
                if arr[x][y] == arr[new_x][new_y] and not checked[new_x][new_y]:
                    q.append((new_x, new_y))
                    checked[new_x][new_y] = True




N = int(input())
arr =[]
for i in range(N):
    arr.append(list(input()))

checked = [[False for _ in range(N)] for _ in range(N)]
q = deque()
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]

cnt1, cnt2 = 0,0
for i in range(N):
    for j in range(N):
        if checked[i][j] == False:
            dfs(i, j)
            cnt1 += 1

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

checked = [[False for _ in range(N)] for _ in range(N)]

for i in range(N):
    for j in range(N):
        if checked[i][j] == False:
            dfs(i, j)
            cnt2 += 1

print(cnt1, cnt2)