백준 10026번: 적록색약 - 파이썬(DFS)

dfs로 탐색문제이다.

 

dfs는 재귀,스텍 자료구조를 이용하는 알고리즘인데

어짜피 같은 원리이지만 나는 주로 재귀를 사용해서 문제를 푼다.

 

dfs알고리즘은 문제를 반복적으로 풀어보게 되면 익숙해질것이고

이 문제는 적록색약(녹색과 빨간색을 구분 못하는 사람)을 신경써서 풀어줘야 하는데

나는 그냥 graph를 딥카피 한후에 R를 G로 바꿔버렸다.

 

반복문을 많이 쓰게 되서 시간초과가 날까 걱정이 되기도 했는데 

일단 통과는 되었다. :)

 

import copy
import sys
sys.setrecursionlimit(100000)
n = int(input())
graph = []
for _ in range(n):
    i = list(map(str,input()))
    graph.append(i)

graph2 = copy.deepcopy(graph)

# 상하좌우
dx = [0,0,-1,1]
dy = [1,-1,0,0]

cnt = 0

def dfs(color,graph,v):
    x = v[0]
    y = v[1]
    if graph[v[0]][v[1]] == 'V':
        return True
    elif graph[v[0]][v[1]] == color:
        graph[v[0]][v[1]] = 'V'
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                dfs(color,graph,[nx,ny])

    

# 적록색약이 아닌 사람
cnt = 0
for x in range(n):
    for y in range(n):
        v = [x,y]
        for color in ['R','G','B']:
            if graph[x][y] == color:
                cnt += 1
                dfs(color,graph,v)

# 적록색약인 사람
cnt_obstacle = 0
for x in range(n):
    for y in range(n):
        if graph2[x][y] == 'R':
            graph2[x][y] = 'G'
for x in range(n):
    for y in range(n):
        v = [x,y]
        for color in ['G','B']:
            if graph2[x][y] == color:
                cnt_obstacle += 1
                dfs(color,graph2,v)


print(cnt,cnt_obstacle)