[백준] 10026- 적록색약 (python 파이썬)

백준 10026 문제 바로가기

풀이 코드

import sys

n = int(input())  # 길이
sys.setrecursionlimit(100000)

graph = [list(map(str, input())) for _ in range(n)]
temp_graph = graph  # 색맹인 사람을 위한 좌표평면

not_weak_visited = [[0] * n for _ in range(n)]  # 색맹이 아닌사람
weak_visited = [[0] * n for _ in range(n)]  # 색맹인 사람

not_weak_cnt = 0  # 색맹이 아닌사람
weak_cnt = 0  # 색맹인 사람

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


def not_weak_dfs(x, y):  # 색맹이 아닌 사람일 경우
    not_weak_visited[x][y] = 1

    for d in range(4):
        nx = dx[d] + x
        ny = dy[d] + y
        if 0 <= nx < n and 0 <= ny < n:  # 범위를 벗어나지 않고
            if not_weak_visited[nx][ny] == 0 and graph[x][y] == graph[nx][ny]:
                not_weak_dfs(nx, ny)


def weak_dfs(x, y):  # 색맹일 사람의 경우
    weak_visited[x][y] = 1

    for d in range(4):
        nx = x + dx[d]
        ny = y + dy[d]
        if 0 <= nx < n and 0 <= ny < n:
            if weak_visited[nx][ny] == 0 and graph[nx][ny] == graph[x][y]:
                weak_dfs(nx, ny)


for i in range(n):  # 색맹이 아닌 사람일 경우
    for j in range(n):
        if not_weak_visited[i][j] == 0:
            not_weak_dfs(i, j)
            not_weak_cnt += 1

for i in range(n):  # 색맹인 사람일 경우, temp_graph를 사용하는데 초록색을 전부 빨간색으로 변경한 후 dfs 적용
    for j in range(n):
        if temp_graph[i][j] == 'G':
            temp_graph[i][j] = 'R'

for i in range(n):  # 색맹인 사람일 경우, dfs 시작
    for j in range(n):
        if weak_visited[i][j] == 0:
            weak_dfs(i, j)
            weak_cnt += 1

print(not_weak_cnt, weak_cnt)

굉장히 복잡하게 푼 것 같아서 조금 만족스럽지는 못하지만... 그래도 이해를 말끔히 해서 좀 홀가분하다!! 이 문제의 경우 색맹인 사람과 아닌 사람의 경우를 나눠서 출력을 하라고 한다.
그래서 난 각 경우를 나눠서 dfs 함수를 만든 후 적용시켜서 cnt를 증가시켰다

색맹이 아닌 사람일 경우는 기존에 dfs를 했던 방식대로 방문하면 1로 바꿔주고 다만 여기선 방문하지 않았던 곳이라도 같은 색이어야 탐색을 한다는 조건이 붙어줘야 한다.

색맹인 사람일 경우에는 입력받은대로의 그래프를 그대로 쓰기보다는 문제에서 나온대로 빨간색과 초록색을 동일하게 취급하기에 초록색이 나온 부분을 전부 빨간색으로 바꿔주고 dfs를 적용시켰다
dfs를 적용시키는 부분은 동일하였다.

사실 하나의 dfs로 푼 사람들도 있으신 것 같아서 찾아봤는데 아직은 다 이해를 못해서 우선 이렇게 풀고 다른 분들의 풀이도 이해하고 있다 !!

회고

기존의 dfs 문제에서 약간의 조건식이 붙은 문제인거같다! 확실히 근데 문제를 풀수록 dfs도 거의 동일하게 풀이가 시작되는거 같아서 겁먹은게 조금 사라지는거 같다 !! 그래도 여전히 어렵기 때문에 문제도 꾸준히 풀면서 이해를 완벽하게 하자!