[백준/BOJ] 10026번 : 적록색약 _Python

10026번: 적록색약

 

>문제

 

>접근방법

dfs로 풀었다. 구역 전체를 탐색하면서 상하좌우를 방문해서 이전 문자와 같으면 다시 상하좌우 탐색 재귀를 반복하는 식으로. 구역 전체 탐색을 총 두 번 하는데 처음 탐색할 때 G인 값은 R로 바꿔준다. 그리고 바꾼 구역을 두 번째로 탐색할 때의 값은 적록색약이 있는 사람의 기준이 된다.

 

 

>풀이법

 주석으로 대체

 

 

>코드

import copy
import sys
# 런타임에러(재귀오류) 방지
sys.setrecursionlimit(10**6)

# 상하좌우 탐색용 인덱스
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# 구역 개수 세는 함수
def dfs_rec(x, y, matrix, visit_T):
    visit_T[x][y] = 1
    for i in range(4):
        a, b = dx[i]+x, dy[i]+y
        # a, b가 구역 내의 범위이면서 같은 문자일 때
        if 0 <= a < n and 0 <= b < n and visit_T[a][b] == 0 and matrix[a][b] == matrix[x][y]:
            # 상하좌우 탐색 반복(재귀 호출)
            dfs_rec(a, b, matrix, visit_T)
            
n = int(input())
#일반용과 적록색약용 각각 두 개 씩 만든다.
rgb = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
rgb2 = copy.deepcopy(rgb)
visit = [[0]*n for _ in range(n)]
visit2 = copy.deepcopy(visit)
cnt1, cnt2 = 0, 0

# 일반인 기준 탐색 루프
for j in range(n):
    for k in range(n):
    	# 적록색약용 rgb그래프에서 모든 G를 R로 바꿔준다.
        if rgb2[j][k] == 'G':
            rgb2[j][k] = 'R'
        # 아직 방문 전이면
        if visit[j][k] == 0:
        	# 구역 개수 세기
            dfs_rec(j, k, rgb, visit)
            cnt1 += 1
            
# 적록색약인 기준 탐색 루프
for j in range(n):
    for k in range(n):
    	# 아직 방문 전이면
        if visit2[j][k] == 0:
        	# 구역 개수 세기
            dfs_rec(j, k, rgb2, visit2)
            cnt2 += 1

print(cnt1, cnt2)

 

 

>결과

 

 

>결론 

아 탁이 무거워. 다리에 피 안통한다..