[Python] 백준 10026 적록색약

문제

로그인

입력

• 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 100)
• 둘째 줄부터 N개 줄에는 그림이 주어진다.

출력

• 적록색약이 아닌 사람이 봤을 때의 구역의 개수와 적록색약인 사람이 봤을 때의 구역의 수를 공백으로 구분해 출력한다.

입력 예제

5
RRRBB
GGBBB
BBBRR
BBRRR
RRRRR

출력 예제

4 3

문제 풀이

• 먼저 적록색맹인 경우와 아닌 경우 두 가지로 나눠서 탐색을 진행해야 한다.
• 적록색맹인 경우 빨간색과 초록색을 같은 색으로 인식해야 하므로 그래프의 값이 'R'일 때 'G'로 바꿔주거나, 'G'일 때 'R'로 바꿔서 탐색을 진행한다.
• 아직 방문하지 않았고, 이전에 탐색한 그래프의 값과 같은 색인 경우 탐색을 진행하여 BFS/DFS를 진행한 후, 총 탐색이 진행된 횟수가 총 구역의 횟수이므로 탐색이 진행될 때 마다 카운트 한 후, 총 탐색횟수를 출력한다.

BFS 코드

from collections import deque
dy = [-1,1,0,0]
dx = [0,0,-1,1]
n = int(input())
graph = []
visited = [[False] * n for _ in range(n)]
for _ in range(n):
    graph.append(list(input()))

def bfs(y,x):
    queue = deque()
    queue.append((y,x))
    visited[y][x] = True
    while queue:
        y,x = queue.popleft()
        for i in range(4):
            ny = y + dy[i]
            nx = x + dx[i]
            if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and graph[ny][nx] == graph[y][x]:
                visited[ny][nx] = True
                queue.append((ny,nx))
cnt1 = 0
# 적록색약이 아닌 경우
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j)
            cnt1 += 1

# 적록색약인 경우
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'R':
            graph[i][j] = 'G'
cnt2 = 0
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            bfs(i,j)
            cnt2 += 1

print(cnt1, cnt2)

DFS 코드

import sys
sys.setrecursionlimit(10**6)
dy = [-1,1,0,0]
dx = [0,0,-1,1]
n = int(input())
graph = []
visited = [[False] * n for _ in range(n)]
for _ in range(n):
    graph.append(list(input()))

def dfs(y,x):
    visited[y][x] = 1
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n and not visited[ny][nx] and graph[y][x] == graph[ny][nx]:
            dfs(ny,nx)
cnt1 = 0
# 적록색약이 아닌 경우
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i,j)
            cnt1 += 1

# 적록색약인 경우
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'R':
            graph[i][j] = 'G'
cnt2 = 0
visited = [[False] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if not visited[i][j]:
            dfs(i,j)
            cnt2 += 1

print(cnt1, cnt2)