[CLASS 3]백준 10026번 - 적록색약

10026번 : 적록색약

 

일단 딱 보면 BFS 혹은 DFS라는 것을 알 수 있다. 그리고 이 문제는 나치고는 드물게 아주 쉽게 풀었다..

 

시간 제한은 1초인데(파이썬은 5초) 입력의 조건(1<=N<=100)이 너무 널널해서 BFS를 두번 돌리면 그냥 풀린다. 출제자의 의도가 이게 맞는지는 잘 모르겠지만 어렵지 않게 풀 수 있었다.

 

# dawitblog.tistory.com
from sys import stdin
input = stdin.readline
from collections import deque

n = int(input())
mat = [input().rstrip() for _ in range(n)]
# G를 모두 R로 변경
mat2 = [s.replace('G','R') for s in mat]
dr = [0,0,1,-1]
dc = [1,-1,0,0]

# bfs
def bfs(mat,r,c,visited):
    rgb = mat[r][c]

    queue = deque([(r,c)])
    visited[r][c] = True

    while queue:
        tr, tc = queue.popleft()
        for i in range(4):
            newR = tr + dr[i]
            newC = tc + dc[i]

            if 0<=newR<n and 0<=newC<n and mat[newR][newC]==rgb and not visited[newR][newC]:
                visited[newR][newC] = True
                queue.append((newR,newC))

# 정상인이 보이는 구역
visited = [[False]*n for _ in range(n)]
count = 0
for r in range(n):
    for c in range(n):
        if not visited[r][c]:
            bfs(mat,r,c,visited)
            count += 1

# 적록색약을 가진 사람이 보이는 구역
visited = [[False]*n for _ in range(n)]
rgbCount = 0
for r in range(n):
    for c in range(n):
        if not visited[r][c]:
            bfs(mat2,r,c,visited)
            rgbCount += 1

print(count, rgbCount)

 

풀이는 그냥 처음 입력을 받을 때 리스트를 하나 더 만들어서 모든 G를 R로 바꾼 값을 저장해놓은 뒤, BFS를 간단히 구현하고 두 리스트에 대해 모두 BFS를 돌리면 된다.