https://www.acmicpc.net/problem/10026

문제 이해

1. 입력된 그리드를 모두 탐색해야함
   -> for문

2. 같은 색끼리 인접해있는 영역의 갯수 구하기
   -> 각 요소에서 DFS 혹은 BFS를 통해 최대 영역을 탐색

3. 적록색약인 사람과 아닌 사람 두 가지를 고려
   - 주어진 그리드는 1 $\leq$ N $\leq$ 100 인 N * N 행렬 이므로 그리드의 최대 크기는 10000
   - 메모리, 제한시간 상 똑같은 크기의 그리드를 새로 만들어도 문제 없을 것으로 판단
   -> "G"와 "R"을 둘 중 하나로 통일한 새 그리드 생성

4. 두 그리드에 대해 똑같은 과정 수행

코드

N = int(input())
table_o = [[] for i in range(N)]
table_x = [[] for i in range(N)]

for i in range(N):
    row = input()
    for j in row:
        table_o[i].append(j)
for i in range(N):
    row = table_o[i]
    for j in row:
        if j == "G":
            j = "R"
        table_x[i].append(j)
visited_o = [[0 for i in range(N)] for i in range(N)]
visited_x = [[0 for i in range(N)] for i in range(N)]

c_o = 0
c_x = 0
prev_c = ""
stack = []

for i in range(N):
    for j in range(N):
        if visited_o[i][j]:
            continue
        prev_c = table_o[i][j]
        stack.append((i, j))
        c_o += 1
        while stack:
            p, q = stack.pop()
            if table_o[p][q] != prev_c:
                continue
            if visited_o[p][q]:
                continue
            visited_o[p][q] = 1
            if p - 1 >= 0:
                stack.append((p - 1, q))
            if p + 1 < N:
                stack.append((p + 1, q))
            if q + 1 < N:
                stack.append((p, q + 1))
            if q - 1 >= 0:
                stack.append((p, q - 1))
stack.clear()
for i in range(N):
    for j in range(N):
        if visited_x[i][j]:
            continue
        prev_c = table_x[i][j]
        stack.append((i, j))
        c_x += 1
        while stack:
            p, q = stack.pop()
            if table_x[p][q] != prev_c:
                continue
            if visited_x[p][q]:
                continue
            visited_x[p][q] = 1
            if p - 1 >= 0:
                stack.append((p - 1, q))
            if p + 1 < N:
                stack.append((p + 1, q))
            if q + 1 < N:
                stack.append((p, q + 1))
            if q - 1 >= 0:
                stack.append((p, q - 1))
print(c_o, c_x)

풀이 과정

적록 구분 가능한 경우의 변수는 _o
적록 구분 불가능한 경우의 변수는 _x로 구분
적록 구분 가능한 그리드부터 구현

1. 입력값 받기
   table_o : 입력받은 그리드 N by N 행렬
   for문 사용

2. 탐색을 위한 그리드와 같은 크기의 행렬 정의
   visited_o : 그리드 요소 방문 여부 기록 N by N 행렬

3. 영역의 갯수를 카운트할 변수 정의
   c_o : 새로운 영역 갯수

4. 이제 그리드를 탐색
   이중 for문을 통해 각 요소 탐색

5. 각 요소를 방문했을 때 과정 구현

   • 방문 여부 확인 : visited_o[i][j] 확인
   • 새로 방문하는 요소라면 새로운 영역을 발견했다는 것 : c_o 1 증가
   • 영역 탐색을 위한 DFS :
     stack 배열 정의, DFS 구현을 위한 배열
     stack배열에 현재 i,j 추가
     DFS를 재귀보다는 반복문으로 구현하는걸 선호한다.
     (DFS 생각하면서 visited 배열만 생각했다가 이때 stack 배열도 추가함)
   • 해당 요소의 색을 기준으로 설정 : prev_c 변수에 table[i][j] 할당
     (문제 풀다가 이 과정에서 해당 변수가 필요하다고 생각함 prev_c : 새로운 영역 탐색할 때 기준 색)
   • 추가된 i,j위치를 시작으로 DFS 실행 :
     이때 i,j 기준 상하좌우를 확인해야 하는데 가능한 인덱스의 최소, 최대 범위를 정해야함. 처음에는 예시의 조건을 그대로 넣어 예를들어 p + 1 < 5 라고 하는 실수를 했어서 N이 5가 아닐 때 오답이 나왔었음.
     (혹시 모를 변수 문제에 대비해 i, j 대신 p,q를 새로 정의해서 사용함. 그런데 굳이 그럴 필요 없이 i, j 쓰는게 보기 더 편했을 것. 파이썬에서 변수를 조작할 때면 항상 헷갈린다 ㅠㅠ)
     

적록 구분 불가능한 경우의 그리드 구현
table_x만 "R"과 "G"를 하나로 통일하고 나머지 과정을 동일

생각해본 점
DFS 풀 때 재귀로도 잘 풀 줄 알아야 하는데 아쉽다
인덱스 최소 최대 범위 생각할 때 실수한게 아쉬움 나 왜 예시의 N 크기를 그대로 썼을까
똑같은 행렬을 그대로 한개 더 만들어서 푼게 좀 아쉬움
다른 분들 풀이는 아직 안봤지만 뭔가 더 예쁜 방법이 있지 않을까 그런데 문제에서 N이 엄청 크진 않아서 내 접근도 괜찮다고 위로해본다.