기존 내 코드

시도해보려했던 것

1. 덱을 사용해서 pop 해서 시간복잡도를 줄여보려고 했음

한 방향으로 1,2,3 ... N-1 칸 까지 보내서 탐색 하다가 같은 색의 돌을 발견하게 된다면?

해당 칸까지 가는 길의 색을 동일하게 바꾸겠다.

하지만 실패...

import sys; sys.stdin = open('txt/oselo.txt')
from collections import deque
# 8방향 탐색이 필요하다
dr = [0,1,1, 1, 0,-1,-1,-1] # 1칸 사이에 다른 색 돌을 둬야 되기 때문
dc = [1,1,0,-1,-1,-1, 0, 1]
# dr2 = [0,2,2, 2, 0,-2,-2,-2] # 2칸 사이에 다른 색 돌을 둬야 되기 때문
# dc2 = [2,2,0,-2,-2,-2, 0, 2]
def oselo(arr):
    # one_idx = lst.popleft()
    # q = [one_idx]
    # visited[]
    while dol_arr: # 덱이 존재하는  동안
        r, c, color = dol_arr.popleft() #하나씩 뽑아버린다.
        arr[r-1][c-1] = color # 해당 좌표에 색을 칠한다.
        flag = 0
        for k in range(8):
            for p in range(1,N): # 한변의 길이-1 만큼 이동가능하다
                nr = r-1 + dr[k] * p
                nc = c-1 + dc[k] * p
            # nr2 = r + dr2[k]
            # nc2 = c + dc2[k]
            # 벽체크 와 방향으로 같은 색의 돌이 나올 때 까지 탐색
                if 0< nr<N and 0< nc<N and arr[nr][nc] == arr[r-1][c-1]:
                    # if 0< nr2<=N and 0< nc2<=N and arr[nr2][nc2] == arr[r][c]:
                    for x in range(r-1,nr):
                        for y in range(c-1,nc):
                            arr[x][y] = arr[r-1][c-1] # 같은 색으로 만든다.
                    flag = 1
                    break # 해당방행으로 탐색 종료
        if flag == 0: # 탐색을 마쳤을 때 조건에 맞지 않을 때
            arr[r-1][c-1] = 0

    print(arr)
    return 0
T = int(input())
for tc in range(1,T+1):
    N,M = map(int,input().split()) # N: 보드의 한 변 길이, M = 돌을 놓는 횟수
    arr = [[0] * (N) for _ in range(N)]
    arr[N//2-1][N//2] = 1 #흑
    arr[N//2-1][N//2-1] = 2 # 백
    arr[N//2][N//2-1] = 1 # 흑
    arr[N//2][N//2] = 2 # 백
    # visited = [[0] for _ in range(N)]
    dol_arr = deque()
    for i in range(1,M+1):
        dol = tuple(map(int,input().split()))
        dol_arr.append(dol)
    # r, c, color
    # print(r,c,color)
    # print(arr)
    print(oselo(arr))

도움 받은 코드

https://glory-summer.tistory.com/95 엉아님 코드

from collections import deque
# 8방향 탐색이 필요하다
dr = [0,1,1, 1, 0,-1,-1,-1]
dc = [1,1,0,-1,-1,-1, 0, 1]
def oselo(arr):
    while dol_arr: # 덱이 존재하는  동안
        r, c, color = dol_arr.popleft() #하나씩 뽑아버린다.
        arr[r-1][c-1] = color # 해당 좌표에 색을 칠한다.
        for k in range(8):
            nr = r-1 + dr[k]
            nc = c-1 + dc[k]
            change = [[nr,nc]] # 바로 옆 돌 저장

            # 벽체크 와 해당 방향으로 빈칸이 아닌 다른 색의 돌이 나올 때 마다 change에 저장시킨다.
            while 0<= nr<N and 0<= nc<N and arr[nr][nc] != 0 and arr[nr][nc] != color:
                nr += dr[k]
                nc += dc[k]
                change.append([nr,nc])
            # print(change)
            # change에 있는 좌표들을 벽체크하고 전부 다 바꿔준다.
            # change에 인접좌표 넣으면서 초기화 했기 때문에 무조건 1개 들어있다.
            # nr,nc 좌표에 돌이 없을 수도 있다. 검 흰흰 0
            if len(change) > 1 and 0<= nr<N and 0<= nc<N and arr[nr][nc] != 0:
                for x,y in change:
                    arr[x][y] = color # 해당 좌표의 색을 같은 색으로 맞춘다.
    # print(arr)
    # 갯수 세기
    b_cnt = 0
    w_cnt = 0
    for i in range(N):
        for j in range(N):
            if arr[i][j] == 1:
                b_cnt += 1
            elif arr[i][j] == 2:
                w_cnt += 1
    return b_cnt,w_cnt
T = int(input())
for tc in range(1,T+1):
    N,M = map(int,input().split()) # N: 보드의 한 변 길이, M = 돌을 놓는 횟수
    arr = [[0] * (N) for _ in range(N)]
    arr[N//2-1][N//2] = 1 #흑
    arr[N//2-1][N//2-1] = 2 # 백
    arr[N//2][N//2-1] = 1 # 흑
    arr[N//2][N//2] = 2 # 백
    dol_arr = deque()
    for i in range(1,M+1):
        dol = tuple(map(int,input().split()))
        dol_arr.append(dol)

    print(f'#{tc}',*oselo(arr))

느낌

접근 방식에 대해 생각하는 역량을 길러야 겠다.
벽체크를 잘해야 된다.
처음에 검 흰 검 같은 경우만 고려해서 안됐다.