[DFS] 10026번 적록색약 - 골드5

[heerucan]

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

문제 요약

• 적록색약 : R, G을 구분 못함
• 출력값 : 적록색약인 사람이 본 거 / 아닌 사람이 본 거 (공백으로 구분해서 출력)
• 이것도 연결요소 문제, 노드덩어리 개수 찾기

import sys
sys.setrecursionlimit(10**7)

n = int(input())

graph = []
for _ in range(n):
    graph.append(list(input()))

def dfs(x, y):
    # myColor는 현재 내 좌표의 대문자를 의미
    myColor = graph[x][y]
    # 내 현재 위치 방문처리를 해주고 (소문자로 바꿔서 방문처리)
    graph[x][y] = graph[x][y].lower() # 소문자화 라이브러리

    # 내 다음 좌표가 나랑 색이 같은지 체크해서 같으면 dfs돌기
    if x-1 >= 0 and x-1 < n:
        if graph[x-1][y] == myColor:
            dfs(x-1, y)

    if x+1 >= 0 and x+1 < n:
        if graph[x+1][y] == myColor:
            dfs(x+1, y)

    if y-1 >= 0 and y-1 < n:
        if graph[x][y-1] == myColor:
            dfs(x, y-1)

    if y+1 >= 0 and y+1 < n:
        if graph[x][y+1] == myColor:
            dfs(x, y+1)

normal = 0
jaejun = 0

# 적록색약 아닌 사람 체크하기
for i in range(n):
    for j in range(n):
        # 이미 방문처리된 아이들은 냅두고
        if graph[i][j] == 'r' or graph[i][j] == 'g' or graph[i][j] == 'b':
            continue
        # 처음 방문하는 아이들만 counting -> 그게 첫 dfs 아이들이니까!
        else:
            dfs(i,j)
            normal += 1

# 아닌 사람 체크 후 소문자로 바뀐 graph -> 대문자화 + R -> G로 변경
for i in range(n):
    for j in range(n):
        graph[i][j] = graph[i][j].upper()
        if graph[i][j] == 'R':
            graph[i][j] = 'G'


# 적록색약 체크하기
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'g' or graph[i][j] == 'b':
            continue
        else:
            dfs(i,j)
            jaejun += 1

print(normal, jaejun)

문풀

1. 그래프 범위 지정
2. 현재 내 좌표 방문처리
3. 내 상하좌우 좌표들이 나랑 색이 같다면 dfs 돌릴 거니까 같은지 체크해주기

이런 식으로 코드를 짤 수 있는데

• 그래프 범위 지정하기보다 해당 풀이 코드에서는 다음좌표가 그래프 범위 내에 있는지 체크해준 후
• 다음 좌표가 나랑 색이 같은지 체크하고
• 같다면 dfs를 돌렸다.

어려웠던 점이 덩어리 카운팅

for i in range(n):
    for j in range(n):
        # 이미 방문처리된 아이들은 냅두고
        if graph[i][j] == 'r' or graph[i][j] == 'g' or graph[i][j] == 'b':
            continue
        # 처음 방문하는 아이들만 counting -> 그게 첫 dfs 아이들이니까!
        else:
            dfs(i,j)
            normal += 1

• 그래프를 돌면서 방문처리 시에 소문자로 바꿔주는데 그 말은 즉, 처음 방문하는 아이들은 대문자일 것이다. 그럼 그 아이들 기준으로 처음 dfs가 돌면서 상하좌우 같은 색상끼리 묶음이 되는 거기에 그 경우에 counting을 해준다.
• 이 부분은 생각하지 못한 부분이다. 기존 dfs 문제는 1 또는 0으로 이뤄져서 분기처리에서 생각이 간단했기 때문에... 후ㅠㅠ
• 기존 상하좌우 체크하는 코드가 for문을 통해 단순했는데 저렇게 8줄의 코드로 이뤄진 줄은 몰랐다. 그냥 외웠을 뿐.. 여튼 이해하자..

파이썬이 제공하는 라이브러리 적극 사용

• 방문처리를 소문자화해주는 걸로 했는데 lower()을 사용하면 6줄의 코드가 더 간결해진다.
  graph[x][y] = graph[x][y].lower()

if graph[x][y] == 'R':
    graph[x][y] = 'r'
    
if graph[x][y] == 'G':
    graph[x][y] = 'g'

if graph[x][y] == 'B':
    graph[x][y] = 'b'