[백준/Python] 10026번(그래프, BFS, DFS)_적록색약

📌문제 유형

그래프 이론, 그래프 탐색, DFS, BFS (골드5)

 

📌문제

10026번: 적록색약

 

📌나의 문제풀이

- Recursion Error 막기 위해서는 Recursion 횟수 늘려주기

import sys
sys.setrecursionlimit(10000)
                      
n = int(input())
maps = []
rg = []

for _  in range(n):
    li = input()
    maps.append(list(map(str,li)))
    li_ = li.replace('R','G')
    rg.append(list(map(str,li_)))


def dfs(l,x,y,c):
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
            if l[nx][ny] == c :
                l[nx][ny] = 'X'
                dfs(l,nx,ny,c)

cnt_1 = 0
cnt_2 = 0
for x in range(n):
    for y in range(n):
        # 정상인
        if maps[x][y] != 'X':
            color = maps[x][y]
            maps[x][y] = 'X'
            dfs(maps,x,y,color)
            cnt_1 += 1

for x in range(n):
    for y in range(n):
        # 적록색약
        if rg[x][y] != 'X':
            color = rg[x][y]
            rg[x][y] = 'X'
            dfs(rg,x,y,color)
            cnt_2 += 1
        
print(cnt_1, cnt_2)

 

📌 다른사람의 문제풀이

- BFS 풀이

[백준] 10026. 적록색약 / python 파이썬

from collections import deque

def BFS(x,y):
    q.append((x,y))
    dx = [-1,0,1,0]
    dy = [0,1,0,-1]
    visited[x][y] = 1
    while q:
        x, y = q.popleft()
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]
            # 인덱스 범위 안에 있으면서, 같은 색이면서, 방문 안한 경우
            if 0<=nx<N and 0<=ny<N and a[nx][ny] == a[x][y] and not visited[nx][ny]:
                visited[nx][ny] = 1  # 방문체크 후 큐에 넣음
                q.append((nx,ny))


N = int(input())
a = [list(input()) for _ in range(N)]
q = deque()

# 적록색약 아닌 경우
visited = [[0] * N for _ in range(N)]
cnt1 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:  # 아직 방문 안한 경우만 체킹
            BFS(i,j)
            cnt1 += 1

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

visited = [[0] * N for _ in range(N)]
cnt2 = 0
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            BFS(i,j)
            cnt2 += 1

print(cnt1, cnt2)

 

📌 리뷰 

- 적록색약인 경우, R을 G로 바꿔서 탐색해야함 
(R, G count 중 큰 것 설정하면 다른 것을 인식하기 때문에 개수 안 맞음!)

- Recursion 개수가 적어서 그냥 넣으면 Recursion Error난다ㅠ 개수 늘리기