Search

[백준 10026] 적록색약

[백준 10026] 적록색약

문제 요약

주어진 그래프에서 구역의 갯수를 구해라!
각 칸에는 R(빨강), G(초록), B(파랑) 그림이 있음.
같은 색상이 상하좌우 인접시 같은 구역
단, 일반적인 경우적록색약의 경우, 두 가지 케이스로 나눠서 구역을 각각 구해야 한다!
적록색약? : 빨강과 초록을 같은 색으로 인식

알고리즘 : DFS / BFS

1.
구역 갯수 구하는 문제는 DFS로 푸는 습관이 들어 DFS를 선택

풀이

두 가지의 함수 구현
DFS 함수
그래프 완전탐색에 사용
현재 탐색 위치 상하좌우 인접 위치를 변수로 재귀적으로 DFS 함수 실행
방문한 위치라면 visted 배열에서 방문 처리
모든 재귀가 끝나면 True 반환
counting 함수
일반적인 경우, 적록색약의 경우 두번 나눠서 구역 갯수를 구하는 문제라 카운트 함수를 구현해서 반복 사용
blind 매개 변수 값으로 일반의 경우 False, 적록색약의 경우 True가 들어감
True인 경우, 서로 구별되지 않도록 그래프의 모든 R 값을 G로 변경
그래프를 완전탐색하며 모든 위치에서 DFS 함수 실행
그 반환 값이 True 라면 하나의 구역 파악이 완료됨을 의미하므로 cnt 변수 +1
출력에 사용할 수 있도록 최종적으로 cnt 값을 반환

풀이 소스 코드

import sys sys.setrecursionlimit(10**9) si = sys.stdin.readline # DFS 함수 def dfs(x, y, target): if 0 <= x < n and 0 <= y < n and graph[x][y] == target and not visited[x][y]: visited[x][y] = True dfs(x - 1, y, target) dfs(x + 1, y, target) dfs(x, y - 1, target) dfs(x, y + 1, target) return True # 카운트 함수 def counting(blind): global visited visited = [[False] * n for _ in range(n)] cnt = 0 # 적록색약의 경우 if blind: for i in range(n): for j in range(n): if graph[i][j] == 'R': graph[i][j] = 'G' for i in range(n): for j in range(n): if dfs(i, j, graph[i][j]) == True: cnt += 1 return cnt n = int(si()) graph = [list(map(str, si().rstrip())) for _ in range(n)] print(counting(False), counting(True))
Python

포인트

DFS구역 갯수 구하기 문제에 익숙하다면 그렇게 어렵지는 않을 것
일반적인 구역 갯수 구하기 문제에, 적록색약의 경우를 구현하는 부분이 추가된 문제