[백준] 10026 - 적록색약 [Python(파이썬)]

문제

www.acmicpc.net/problem/10026

10026번: 적록색약

 

풀이

간단한 그래프 탐색 문제였다.

기본적으로 DFS로 풀이하되 적록색약자의 경우엔 탐색시에 조건을 추가하여 현재 방문한 노드가 'G'라면 'R'인 노드를 탐색할 수 있고, 'R'이라면 'G'인 노드를 탐색할 수 있게끔 했다.

 

코드

import sys
sys.setrecursionlimit(10**6)

def dfs(y, x):
    visited[y][x] = 1
    
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            if g[y][x] == g[ny][nx] and not visited[ny][nx]:
                dfs(ny, nx)


def cw_dfs(y, x):
    cw_visited[y][x] = 1
    
    for i in range(4):
        ny, nx = y+dy[i], x+dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            cur = g[y][x]
            if g[y][x] == g[ny][nx] and not cw_visited[ny][nx]:
                cw_dfs(ny, nx)
            elif g[y][x] != g[ny][nx] and not cw_visited[ny][nx]:
                if cur == 'G':
                    if g[ny][nx] == 'R':
                        cw_dfs(ny, nx)
                elif cur == 'R':
                    if g[ny][nx] == 'G':
                        cw_dfs(ny, nx)
    
    
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]

n = int(sys.stdin.readline().strip())
g = [[x for x in sys.stdin.readline().strip()] for _ in range(n)]

visited = [[0 for _ in range(n)] for _ in range(n)]
cnt = 0
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j)
            cnt += 1

cw_visited = [[0 for _ in range(n)] for _ in range(n)]
cw_cnt = 0
for i in range(n):
    for j in range(n):
        if not cw_visited[i][j]:
            cw_dfs(i, j)
            cw_cnt += 1

print(cnt, cw_cnt)