[BOJ 10026] 적록색약 (Python)

문제

적록색약

---

문제 해설

BFS 또는 DFS를 활용하는 문제입니다. 이 문제 역시 깊이 제한을 해제해야 DFS로 풀 수 있습니다.

1. graph를 완전 탐색하여 방문하지 않은 곳을 발견하면 DFS 실행.
2. DFS는 4방 탐색을 시작하는데, 같은 문자를 만나면 재귀호출을 하는 방식으로 짠다.
3. DFS가 호출될 때 마다 answer+1
4. 색약인 경우 graph에서 R와 G를 통합한다.(R -> G)
5. 2,3 실행

---

풀이 코드

# 5:02
import sys

sys.setrecursionlimit(100000)

input = sys.stdin.readline
answer = 0
graph = []
n = int(input())
visited = [[False] * n for _ in range(n)]

for _ in range(n):
    graph.append(list(map(str, input().rstrip())))


def dfs(x, y, char):
    global n
    dx = -1, 0, 1, 0
    dy = 0, 1, 0, -1
    visited[x][y] = True

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


for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j, graph[i][j])
            answer += 1
print(answer, end=" ")
answer = 0
for i in range(n):
    for j in range(n):
        visited[i][j] = False
        # R -> G
        if graph[i][j] == "R":
            graph[i][j] = "G"

for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i, j, graph[i][j])
            answer += 1

print(answer)

---