[백준/Python] 10026번 적록색약

알고리즘 설명

이 문제는 그래프 탐색 문제로, 각 칸을 그래프의 노드로, 인접한 칸을 연결된 노드로 간주하여 해결할 수 있다.

DFS(깊이 우선 탐색)는 시작 노드에서 가장 멀리 있는 노드를 우선적으로 탐색하는 방식이다. 스택을 사용하여 구현할 수 있으며, 이 문제에서는 스택에 현재 위치를 넣고, 스택이 비어있지 않는 동안 계속해서 스택의 마지막 요소를 꺼내어 그 위치의 인접한 위치를 탐색합니다.

이 문제에서는 같은 색상의 영역을 찾는 것이 목표이므로, 같은 색상의 인접한 칸을 DFS로 탐색하여 같은 색상의 영역을 찾는다. 이렇게 하면 적록색약인 사람과 아닌 사람이 보는 그림의 차이를 구할 수 있다.

문제

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.

크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

예를 들어, 그림이 아래와 같은 경우에

RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다. (빨강-초록 2, 파랑 1)

그림이 입력으로 주어졌을 때, 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)

둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

문제 접근

• 일단 stack으로 위치를 저장하고 pop, append하는 아이디어는 gpt가 알려줬다. 원래는 현재 위치를 저장하고 업데이트하는 아이디어로 접근했는데 재귀 깊이 문제로 잘 안 풀렸다… 다른 사람 풀이 중에서 재귀 깊이를 정할 수 있다는 것을 알았음.

• 전에 DFS 문제 풀 때 북, 동, 남, 서 방향을 함수로 만들어서 0, 1, 2, 3으로 아웃풋 내줘서 방향벡터 dx[d], dy[d] 이런 식으로 풀었다.

• 근데 for문의 반복 변수 i로 방향 벡터로 탐색할 방향을 처리할 수 있다는 것을 알게 되었음

문제 풀이

• dfs 함수는 x, y 좌표와 해당 처리할 color를 매개변수로 받는다.

• stack에 위치를 저장하고 stack이 비어있지 않는 동안 반복한다.

• 해당 위치의 북, 동, 남, 서 방향으로 nx, ny가 범위 내에 있고, 방문하지 않았으며, 색깔이 같다면 stack에 nx, ny를 저장한다.

• count_regions함수는 color를 받아서 방문하지 않았고, 매개변수로 받은 색깔이 현재 위치 array[i][j]와 같다면 dfs를 탐색하고, count를 한다. 그리고 count를 반환한다.

• 그래서 sum1은 count_resions에 R, G, B를 카운트한 합계를 저장하고

• sum2는 visited 변수를 초기화하고, G를 R로 array를 업데이트 한 후 카운트한 합계를 저장한다.