[python] 백준 10026 적록색약

https://www.acmicpc.net/problem/10026

10026번: 적록색약

 

문제 해결

• 그래프를 만들어 구역을 나누는 개수를 세는 문제
• 적록색약인 사람은 'R' 과 'G'를 같은 색으로 본다.
• bfs()를 이용하면 금방 풀 수 있는 문제 (DFS도 좋지만 이렇게 이동하는 문제는 BFS가 편한 것 같습니다.)
• 사실 두 번 사용하는거 말고 다른 방법이 있나 생각을 해봤지만... 글쎄...?

 

CODE

import sys
from collections import deque
input = sys.stdin.readline
n = int(input())
graph = [[c for c in str(input().rstrip())] for _ in range(n)]
normal_visited = [[False for _ in range(n)] for _ in range(n)]
move = [(-1,0), (0,1), (0,-1), (1,0)]
def bfs(x,y):
    que = deque()
    que.append((x,y))
    normal_visited[x][y] = True
    while que:
        r, c = que.popleft()
        for next in move:
            if 0<= r + next[0]<n and 0<= c+ next[1]<n:
                if graph[r][c] == graph[r+next[0]][c+next[1]] and normal_visited[r+next[0]][c+next[1]] == False:
                    normal_visited[r+next[0]][c+next[1]] = True
                    que.append((r+next[0], c+next[1]))
ans_1= 0
abnormal_visited = [[False for _ in range(n)] for _ in range(n)]
ans_2 = 0
def sub_bfs(x,y):
    que = deque()
    que.append((x,y))
    abnormal_visited[x][y] = True
    while que:
        r, c= que.popleft()
        for next in move:
            if 0<= r + next[0]<n and 0<= c+ next[1]<n:
                if graph[r][c] in ['R','G'] and graph[r+next[0]][c+next[1]] in ['R','G'] and abnormal_visited[r+next[0]][c+next[1]] == False:
                    abnormal_visited[r+next[0]][c+next[1]] = True
                    que.append((r+next[0], c+next[1]))
                elif graph[r][c] == graph[r+next[0]][c+next[1]] and abnormal_visited[r+next[0]][c+next[1]] == False:
                    abnormal_visited[r+next[0]][c+next[1]] = True
                    que.append((r+next[0], c+next[1]))
for i in range(n):
    for j in range(n):
        if normal_visited[i][j] == False:
            ans_1 += 1
            bfs(i,j)
        if abnormal_visited[i][j] == False:
            ans_2 += 1
            sub_bfs(i,j)
print(ans_1, ans_2)