[백준/Python] 10026 적록색약

문제 링크

10026번: 적록색약

 

문제 풀이

• 위 문제는 dfs, bfs 두 가지 방법으로 모두 풀이가 가능하다.
• 적록색약이 아닌 사람은 R, G, B 모두 다르게 인식하지만, 적록색약인 사람은 R, G를 구분하지 못하므로, 입력 받은 리스트에서 G인 부분을 R로 바꾸어 새로운 리스트를 생성하였다.
• 방문 처리 리스트(visited)를 통해서 시작 위치를 방문하지 않았으면 함수(dfs, bfs)를 실행한다. 이때, 해당 함수는 시작 위치와 동일한 위치에 대해서만 방문 처리를 하게 된다. 이후 해당 과정이 끝나면, result 값을 1 증가하는데, 이는 같은 색으로 인식 하는 하나의 부분의 개수를 세는 것과 동일하다.
• 반복문이 모두 끝날 때까지 동일한 방법으로 방문 처리 후, 부분의 개수를 카운트하여 최종적으로 적록색약이 아닌 사람과, 적록색약인 사람이 보는 부분의 개수를 출력한다.

 

전체 코드

# dfs 풀이
import sys

sys.setrecursionlimit(10 ** 7)

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

n = int(sys.stdin.readline())
l = [list(sys.stdin.readline().strip()) for _ in range(n)]
l2 = [["R" if j == "G" else j for j in i] for i in l]

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

visited1 = [[False] * n for _ in range(n)]
visited2 = [[False] * n for _ in range(n)]

res1 = 0
res2 = 0
for i in range(n):
    for j in range(n):
        if not visited1[i][j]:
            dfs(i, j, l, visited1)
            res1 += 1
        if not visited2[i][j]:
            dfs(i, j, l2, visited2)
            res2 += 1

print(res1, res2)


# bfs 풀이
import sys
from collections import deque

def bfs(x, y, l, v):
    queue = deque()
    queue.append((x, y))
    v[x][y] = True
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n and not v[nx][ny] and l[x][y] == l[nx][ny]:
                v[nx][ny] = True
                queue.append((nx, ny))

n = int(sys.stdin.readline())
l = [list(sys.stdin.readline().strip()) for _ in range(n)]
l2 = [["R" if j == "G" else j for j in i] for i in l]

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

visited1 = [[False] * n for _ in range(n)]
visited2 = [[False] * n for _ in range(n)]

res1 = 0
res2 = 0
for i in range(n):
    for j in range(n):
        if not visited1[i][j]:
            bfs(i, j, l, visited1)
            res1 += 1
        if not visited2[i][j]:
            bfs(i, j, l2, visited2)
            res2 += 1

print(res1, res2)