[백준] 10026번 적록색약 - (Python)

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

10026번: 적록색약

 

DFS를 통해 구현하는 문제. 해당문제와 유사한 문제가 많았기 때문에, 참고해서 푼다면 금방 풀 수 있었던 문제입니다. 단, 3 구역을 각각 처리하고, 이를 2 구역으로 나누는 부분처리만 할 수 있다면 어렵지 않게 풀 수 있었던 문제입니다.

※ 고려사항

1. 입출력 처리

2. DFS 처리

3. 정상, 색약 카운팅

---

1. 입출력 처리

해당 문제는 기존의 그래프문제와 살짝 입력구문이 다릅니다. 바로 띄어쓰기 없이 해당문자를 구분해야 한다는 점 입니다. 그러나 python은 이런 indexing이 잘 되어있습니다. rstrip() 메소드를 통해서 구분해 줄 수 있습니다. 

다음으로는 방문처리입니다. 해당 위치를 방문했는지 유무를 판단하기 위해, 해당 행렬과 동일한 크기의 방문행렬을 생성해 줍니다.코드는 다음과 같습니다.

 

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 그래프 저장
graph = [list(input().rstrip()) for _ in range(n)]

# 방문여부 판단
visited = [[False] * n for _ in range(n)]

 

2. DFS 처리

solved.ac의 class 순서대로 문제를 푸셨다면, 아마 이와 유사한 문제를 1번쯤은 접해보셨을 거라고 생각됩니다.

1012번 유기농 배추와 비슷한 매커니즘을 가지고 있습니다. 또는 7576번 토마토와 유사합니다.

해당문제를 풀지 않으셨다면, 함께 풀어보는것을 권장드립니다. 따라서 해당 범위를 초과하거나, 색깔이 동일한지 유무, 이미 방문되었는지 유무 3가지를 판단해 주면 됩니다.

코드는 다음과 같습니다.

# DFS
def dfs(x, y, color):

    # 범위를 벗어나면 False
    if x >= n or x <= -1 or y >= n or y <= -1:
        return False

    # 이미 방문된 노드라면 False
    if visited[x][y] == True:
        return False

    # 현재위치 color 저장
    c = graph[x][y]

    # 현재위치와 인접노드의 색이 동일할 때
    if color == c:
        
        # 방문처리 후, 상하좌우
        visited[x][y] = True
        dfs(x-1, y, c)
        dfs(x, y-1, c)
        dfs(x+1, y, c)
        dfs(x, y+1, c)
        return True

    return False

 

3. 정상, 색약 카운팅

해당 방문노드는 DFS구문을 1번 통과하면 False 에서 True로 변경됩니다. 그렇기 때문에 다시금 초기화하는 방법이 필요합니다. 또 색약은 G를 R로 교체해서 판단해도 무방하기 때문에 행렬의 G를 R로 교체한 후, DFS를 통과하게 합니다.

코드는 다음과 같습니다.

# 정상, 색맹 변수
normal, abnormal = 0

# 정상 카운팅
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            if dfs(i, j, graph[i][j]) == True:
                normal +=1

# G를 R로 교체, 방문배열 초기화
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'
        visited[i][j] = False

# 색맹 카운팅
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            if dfs(i, j, graph[i][j]) == True:
                abnormal +=1  

# 출력
print(normal, abnormal)

---

전체코드

import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(10000)
n = int(input())

# 그래프 저장
graph = [list(input().rstrip()) for _ in range(n)]

# 방문여부 판단
visited = [[False] * n for _ in range(n)]

# DFS
def dfs(x, y, color):

    # 범위를 벗어나면 False
    if x >= n or x <= -1 or y >= n or y <= -1:
        return False

    # 이미 방문된 노드라면 False
    if visited[x][y] == True:
        return False

    # 현재위치 color 저장
    c = graph[x][y]

    # 현재위치와 인접노드의 색이 동일할 때
    if color == c:
        
        # 방문처리 후, 상하좌우
        visited[x][y] = True
        dfs(x-1, y, c)
        dfs(x, y-1, c)
        dfs(x+1, y, c)
        dfs(x, y+1, c)
        return True

    return False

# 정상, 색맹 변수
normal, abnormal = 0

# 정상 카운팅
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            if dfs(i, j, graph[i][j]) == True:
                normal +=1

# G를 R로 교체, 방문배열 초기화
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'G':
            graph[i][j] = 'R'
        visited[i][j] = False

# 색맹 카운팅
for i in range(n):
    for j in range(n):
        if visited[i][j] == False:
            if dfs(i, j, graph[i][j]) == True:
                abnormal +=1  

# 출력
print(normal, abnormal)

---

그래프 문제는 확실히 반복해서 자주 풀다보면, 입출력이나 함수 구현이 금방 떠오르게 됩니다. 아직까지는 메모리나 시간초과 관련해서 처리하는 기술이 부족하다고 판단됩니다. 따라서 그래프 문제를 접근할 때는 다른 글에서도 언급했듯이, DFS, BFS, 재귀 3가지로 반복학습 하는 것이 중요합니다.

설명의 오류나, 궁금하신점은 언제든 피드백해주시면 감사하겠습니다 ^~^