[Python] 백준, 10026(DFS)

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

10026번: 적록색약

개요

- 1, 0과 같은 단순한 원소들로 이루어진 전형적인 자료구조를 탈피한 첫 번째 문항인 것 같다. 따라서 추가적인 조건문의 계산만 더해주면 되므로 사실상 그리 복잡하지는 않다.

- dfs 함수에 부가적인 기능을 넣고 싶지 않아서 답을 도출하는 이중 for문을 조금 길게 작성했다.

- 재귀를 이용하는 dfs에 약하다고 판단해서 스택은 고려하지 않고 푸는 중인데, 맞은 사람 중 런타임이 상위권에 랭크되어 있는 답안들은 주로 bfs/dfs(스택) 풀이들이 많은 것 같다.

- 적록색맹인 사람의 경우에서 독창적인 방법이 떠오르지 않아서 ['R', 'G'] 리스트 안에 요소가 있는지 확인하는 형태의 조건문을 작성했는데, 그리 깔끔해 보이지 않아서 껄끄럽다.

 

추상적 구현

- dfs문은 시작하자마자 주어진 인수의 visit값을 1로 바꾸도록 설정했는데, 이는 난잡한 visit의 등장을 막기 위함이며 재귀 시에 사용되는 dfs 함수는 이미 주어진 인덱스 조건을 만족한 후의 루프이기 때문에 에러의 위험이 없다.

- visit 리스트는 적록색맹인 경우와 아닌 경우를 따로 생각하기 위해서 두가지로 설정했다.

- 위에 언급한 대로, 단순한 원소들의 자료구조들이 아니기 때문에 직전 원소를 기억해야 한다는 조건이 추가되었다. 따라서 dfs를 돌기 전, color 리스트에 직전 원소를 저장해 두었다.

 

# PYTHON CODE

import sys

sys.setrecursionlimit(5000)

n = int(sys.stdin.readline())
tree = [list(sys.stdin.readline().rstrip()) for _ in range(n)]
result = [0, 0]
visit1 = [[0] * n for _ in range(n)]
visit2 = [[0] * n for _ in range(n)]


def dfs_normal(a, b, x, visit):
    visit[b][a] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    for i in range(4):
        nx = a + dx[i]
        ny = b + dy[i]

        if 0 <= nx < n and 0 <= ny < n and tree[ny][nx] in x and visit[ny][nx] == 0:
        	dfs_normal(nx, ny, x, visit)


for i in range(n):
    for j in range(n):
        color = [tree[i][j]]
        if visit1[i][j] == 0:
            dfs_normal(j, i, color, visit1)
            result[0] += 1
        if visit2[i][j] == 0:
            if color == ['R'] or color == ['G']:
                color_list = ['R', 'G']
            else:
                color_list = ['B']
            dfs_normal(j, i, color_list, visit2)
            result[1] += 1

print(result[0], result[1])