[백준/Python] 10026번 적록색약
![[백준/Python] 10026번 적록색약](https://inblog.ai/_next/image?url=https%3A%2F%2Finblog.ai%2Fapi%2Fog%3Ftitle%3D%255B%25EB%25B0%25B1%25EC%25A4%2580%252FPython%255D%252010026%25EB%25B2%2588%2520%25EC%25A0%2581%25EB%25A1%259D%25EC%2583%2589%25EC%2595%25BD%26logoUrl%3Dhttps%253A%252F%252Finblog.ai%252Finblog_logo.png%26blogTitle%3Dcode-with-me&w=1920&q=75)
알고리즘 설명
이 문제는 그래프 탐색 문제로, 각 칸을 그래프의 노드로, 인접한 칸을 연결된 노드로 간주하여 해결할 수 있다.
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를 업데이트 한 후 카운트한 합계를 저장한다.