[백준/10026/파이썬] 적록 색약

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

10026번: 적록색약

BFS/DFS를 조금만 응용하면 되는 문제이다. 항상 DFS/BFS가 가능한지/아닌지 판단하기 위해서 , 시간복잡도를 생각 해줘야 하는데, 이 문제는 연결요소의 갯수를 찾는 문제랑 똑같다.

 

1. 모든 노드를 방문해야하는가? => 아니다. 한 노드를 시작점으로, 방문해서, 방문한 곳은 방문해줄 필요가 없다.(경우의 수가 달라지지않음. 단, R,G,B가 다 구분되게끔 색칠이 된다면, 모든 노드를 방문해야 된다). 즉 , 최악의 경우는 N^2.

 

그리고, 노드를 방문할 때마다,상,하,좌,우는 방문해야하니까,  O(N^2*4) => O(N^2)이다.

 

• 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다.
• 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다.
• 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)

import sys
from collections import deque
input = sys.stdin.readline

N= int(input())
board= [list(input().rstrip()) for _ in range(N)]
v_chk= [[False]*N for _ in range(N)]
dx=(1,0,-1,0)
dy=(0,1,0,-1)
#1<=N<=100
#방문체크를 해서, 최대한 중복을 없애면, bfs/dfs로 가능.
def bfs(y,x,c):
    dq=deque()
    v_chk[y][x] =True
    dq.append((y,x,c))
    while dq:
        y,x,c=dq.popleft()
        for k in range(4):
            ny=y+dy[k]
            nx=x+dx[k]
            if (0<=ny<N and 0<=nx<N) and not v_chk[ny][nx] and board[ny][nx] ==c:
                v_chk[ny][nx] =True
                dq.append((ny,nx,c))
ans=[0,0]
for i in range(N):
    for j in range(N):
        if not v_chk[i][j] and board[i][j] in ['R','G','B']:
            bfs(i,j,board[i][j])
            ans[0] +=1
# 적록색맹 버전으로 바꾸기.
for i in range(N):
    for j in range(N):
        if board[i][j] =="G":
            board[i][j] ="R"

v_chk= [[False]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if not v_chk[i][j] and board[i][j] in ['R','B']:
            bfs(i,j,board[i][j])
            ans[1] +=1

print(ans[0],ans[1])