bfs 시간초과 해결법..

백준 10026 - 적록색약 문제를 bfs로 풀다가..
시간초과 문제에 부딪혔고 여러 시도 끝에 해결하여 기록을 해보려한다.

시간초과를 해결을 위해서는 visited 체크를 어디서 해줄지!! 를 잘 생각해야한다.

시간초과 코드

k = int(s.readline());
input_arr =[];
for i in range(0,k):
    input_arr.append(list(map(str,str(s.readline().strip()) )));

#색약을 위한 배열 (이차원배열의 얕은 복사 - deepcopy())
blind_arr = copy.deepcopy(input_arr)
for i in range(0, k):
    for j in range(0,k):
        #g를 r로
        if (blind_arr[i][j] == 'G'):
            blind_arr[i][j]= 'R'
        
dx=[-1,0,1,0];
dy=[0,-1,0,1];

q=deque();

def bfs(color, arr):
    while q: 
        [x,y]= q.popleft();
        arr[x][y] = -1;
        #상하좌우 이동
        for i in range(0,4):
            _x=x+dx[i];
            _y=y+dy[i];
            if (_x >=0 and _y >=0 and _x <k and _y < k):
                if (arr[_x][_y] == color):
                    #같은 색이면 전개
                    q.append([_x, _y]);
count =0;
blind_count =0;
for i in range(0, k):
    for j in range(0,k):
        if (input_arr[i][j] != -1):
            q.append([i,j]);
            bfs(input_arr[i][j], input_arr);
            count+=1;
          
for i in range(0, k):
    for j in range(0,k):
        if (blind_arr[i][j] != -1):
            q.append([i,j]);
            bfs(blind_arr[i][j], blind_arr);
            blind_count+=1;

print(str(count) + ' ' + str(blind_count))

이 경우에는 arr[x][y] = - 1 즉, 방문체크를 큐에서 pop할 때 한다.
여기서의 문제점은 for문으로 상하좌우 돌면서 큐에 append가 된 좌표의 경우에는 pop이 되기 전까지 (큐에 쌓여있는 상황)는 -1 처리가 되지 않아서 중복으로 여러번 체크 되어 큐에 여러번 들어가게 되는 경우가 생김.
이 경우 값은 제대로 나오지만 시간초과에서 걸림

수정한 코드 (시간초과 x)

# 10026 - 적록색약 (골드5)
from sys import stdin as s
from collections import deque
import copy
#제출 시 주석 필수
s=open("input.txt","rt");

k = int(s.readline());
input_arr =[];
for i in range(0,k):
    input_arr.append(list(map(str,str(s.readline().strip()) )));

#색약을 위한 배열 (이차원배열의 얕은 복사 - deepcopy())
blind_arr = copy.deepcopy(input_arr)
for i in range(0, k):
    for j in range(0,k):
        #g를 r로
        if (blind_arr[i][j] == 'G'):
            blind_arr[i][j]= 'R'
        
dx=[-1,0,1,0];
dy=[0,-1,0,1];

q=deque();

def bfs(color, arr):
    while q: 
        [x,y]= q.popleft();
        #상하좌우 이동
        for i in range(0,4):
            _x=x+dx[i];
            _y=y+dy[i];
            if (_x >=0 and _y >=0 and _x <k and _y < k):
                if (arr[_x][_y] == color):
                    #같은 색이면 전개
                    arr[_x][_y] = -1;
                    q.append([_x, _y]);

count =0;
blind_count =0;
for i in range(0, k):
    for j in range(0,k):
        if (input_arr[i][j] != -1):
            q.append([i,j]);
            color =  input_arr[i][j];
            input_arr[i][j] = -1;
            bfs(color, input_arr);
            count+=1;
q.clear();
for i in range(0, k):
    for j in range(0,k):
        if (blind_arr[i][j] != -1):
            q.append([i,j]);
            color =  blind_arr[i][j];
            blind_arr[i][j] = -1;
            bfs(color, blind_arr);
            blind_count+=1;

print(str(count) + ' ' + str(blind_count))
            

이 경우에는 방문 체크(input_arr[_x][_y] = -1) 를 상하좌우를 도는 for문 내에서 한다. 상하좌우 중 조건에 맞는 좌표 발견시 바로 즉각적으로 방문체크를 해주기때문에 이후 중복으로 체크될 일이 없어 시간효율이 좋다.