[BOJ / Python] 10026번 : 적록색약

문제 제목, 난이도

10026번 : 적록색약, 골드5

---

문제 링크

www.acmicpc.net/problem/10026

10026번: 적록색약

---

코드(Python)

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

n = int(input())
li = []
visited = [[False for i in range(n)] for _ in range(n)]
for _ in range(n) :
    tmp = input().rstrip()
    li.append(tmp)

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

def dfs(x, y, color) :
    for dli in range(4) :
        nx = x + dx[dli]
        ny = y + dy[dli]
            
        if nx >= n or nx < 0 or ny >= n or ny < 0 :
            continue
    
        if li[nx][ny] == color and visited[nx][ny] == False :
            visited[nx][ny] = True
            dfs(nx,ny,color)

def dfs_(x, y, color) :
    for dli in range(4) :
        nx = x + dx[dli]
        ny = y + dy[dli]
            
        if nx >= n or nx < 0 or ny >= n or ny < 0 :
            continue
    
        if li_[nx][ny] == color and visited[nx][ny] == False :
            visited[nx][ny] = True
            dfs_(nx,ny,color)


count = 0
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == False :
            visited[i][j] = True
            count += 1
            dfs(i, j, li[i][j])

li_ = []
for i in range(n) :
    tmp = ''
    for j in range(n) :
        if li[i][j] == 'B' :
            tmp += 'B'
        else :
            tmp += 'G'

    li_.append(tmp)

visited = [[False for i in range(n)] for _ in range(n)]
count_ = 0
for i in range(n) :
    for j in range(n) :
        if visited[i][j] == False :
            visited[i][j] = True
            count_ += 1
            dfs_(i, j, li_[i][j])

# 적록색맹 R = B

print(count, count_)

---

풀이

리스트를 만들고 완전탐색으로 상하좌우를 체크하면서 count 에 1을 더한다.

적록색약 리스트를 하나 더 만들고, 동일하게 실행한다.

---

체크리스트

DFS, 완전탐색

파이썬의 기본 재귀 깊이보다 재귀적으로 많이 호출하는 문제라서 sys.setrecursionlimit(10000) 를 추가해줘야한다. 재귀문제마다 자꾸 까먹음

좀 더럽게 리스트도 두 개 만들고 함수도 두 개 정의하면서 어거지로 풀었는데, n이 100이라서 시간제한 1초에 걸리지 않을 것 같아서 생각나는 대로 풀었다.

리스트 하나만 만들고 함수에서 색약인지 아닌지 구분해서 분기점 만들면 간결하게 만들 수 있을듯 ?