[Python] 10026 - 적록색약

[Gold V] 적록색약 - 10026 

[문제 링크](https://www.acmicpc.net/problem/10026)

🗝️알고리즘 분류

• 그래프 탐색
• 너비 우선 탐색 (BFS)
• 깊이 우선 탐색 (DFS)

---

💻문제 정의

빨간색(R), 초록색(G), 파란색(B) 세 색상이 NxN 크기의 그리드에 칠해져 있다. 일반인이 보았을 때의 구역과 적록색약인 사람이 보았을 때의 구역의 수를 구하는 프로그램을 작성하는 문제이다.

 

💡접근 및 설계

그리드 전체 점을 탐색한다. 방문한 점은 방문 표시를 하고, 방문하지 않은 점에 대해서 그래프 탐색을 실시한다. 한 점을 기준으로 상, 하, 좌, 우를 탐색하여 같은 색상인 경우 탐색을 이어간다. 그래프 탐색이 끝나면 구역의 수 +1을 한다.

 

이후 적록색약인 사람의 경우, R인 영역(또는 G)을 G(또는 R)로 변환 후, 그리드 전체를 탐색한다.

 

✏️알고리즘 풀이

# 너비 우선 탐색

def bfs(x, y):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = True

    while Q:
        cx, cy = Q.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and (graph[nx][ny] == graph[x][y]) and not visited[nx][ny]:
                Q.append([nx, ny])
                visited[nx][ny] = True

# 깊이 우선 탐색

def dfs(x, y):
    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 (graph[x][y] == graph[nx][ny]) and not visited[nx][ny]:
            dfs(nx, ny)

이 문제는 두 가지 그래프 탐색법으로 해결할 수 있다.

 

각 그래프 탐색은 그리드 전체를 탐색하되, 방문하지 않은 점들에 대해서 탐색을 진행하도록 한다.

탐색이 끝나면 구역의 수를 1 증가 시킨다.

 

🗒️제출 코드

# 10026 적록색약 (BFS)

from collections import deque

N = int(input())

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

graph = []
for _ in range(N):
    word = input()
    graph_2 = []
    for ix in word:
        graph_2.append(ix)
    graph.append(graph_2)

def bfs(x, y):
    Q = deque()
    Q.append([x, y])
    visited[x][y] = True

    while Q:
        cx, cy = Q.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if (0 <= nx < N) and (0 <= ny < N) and (graph[nx][ny] == graph[x][y]) and not visited[nx][ny]:
                Q.append([nx, ny])
                visited[nx][ny] = True

# 정상인
non_blind = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)
            non_blind += 1

# 적록색약
for i in range(N):
    for j in range(N):
        if (graph[i][j] == "G"):
            graph[i][j] = "R"

blind = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            bfs(i, j)
            blind += 1

print(non_blind, blind)

# 10026 적록색약 (DFS)

import sys
sys.setrecursionlimit(100000)

N = int(input())

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

graph = []
for _ in range(N):
    word = input()
    graph_2 = []
    for ix in word:
        graph_2.append(ix)
    graph.append(graph_2)

def dfs(x, y):
    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 (graph[x][y] == graph[nx][ny]) and not visited[nx][ny]:
            dfs(nx, ny)

# 정상인
non_blind = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not visited[i][j]:
            dfs(i, j)
            non_blind += 1

# 적록색약
for i in range(N):
    for j in range(N):
        if (graph[i][j] == "G"):
            graph[i][j] = "R"

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

print(non_blind, blind)

---

💭오늘의 회고

해당 문제의 시간 제한은 1초. 입력 값 제한은 (1 ≤ N ≤ 100) 이다.

즉, 완전 탐색 후 그래프 탐색을 여러 번 하여도 시간이 넉넉하게 남는다.

 

시간 제한에 구애받지 않고 편하게 탐색 기법을 여러 번 사용해볼 수 있는 문제였다.