[백준 10026 적록색약] 파이썬 BFS 너비 우선 탐색 풀이

적록색약 문제

10026번: 적록색약

RGB 3가지 문자로 이루어진 N * N 보드판이 주어질때 일반사람과 적록색약인 사람이 보는 구역의 수를 각각 구하는 문제입니다. 적록색약은 R과 G를 하나의 색으로 보입니다. 즉, 아래와 같이 구역이 나뉘게 됩니다.

 

문제 풀이

2차원 배열의 영역을 구하는 문제로 BFS 너비 우선 탐색 알고리즘을 사용해서 풀면 될것으로 판단했습니다. 단, 2가지 경우가 발생하기 때문에 2가지 버전의 배열을 만들어주고 탐색하는 방식을 선택했습니다. N의 최대 값이 100이므로 배열을 하나 더 생성하는데 크게 무리가 없는것으로 판단했습니다.

 

1. 입력 받은 배열로 적록색약용 배열 생성 --> R,G : 1      B : 2
2. 각각 배열의 크기가 같으므로 동시에 BFS 순회 

 

2차원 배열이 N * N 일때 시간 복잡도는 O(N^2)으로 계산 됩니다.

배열의 각각 위치를 순회하면서 영역 여부를 확인하고 방문했을 경우 0으로 표시하기 때문에 이미 들린 경우 연산작업을 건너뜁니다. 2개의 배열을 탐삭하여 2*N^2이지만 상수는 생략됩니다.

 

 

파이썬 코드