• bfs를 통해 일반인은 같은 그림만 한 구역으로 보게, 적록색약은 R,G를 같은 구역으로 볼 수 있도록 하였다.

from collections import deque
import copy
N = int(input())
arr = [list(input()) for _ in range(N)]
acc = copy.deepcopy(arr) # 적록색약용 배열 복사본 생성
area = 0
def bfs(y,x,tmp,blind): # y,x,색깔,적록색약 유무
    q = deque([(y,x)])

    directy = [-1,1,0,0]
    directx = [0,0,-1,1]
    while q:
        y,x = q.popleft()

        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= N or dx < 0:
                continue
            if blind == 1 and (tmp == 'R' or tmp == 'G'): # 적록색약이면서 구역의 색깔이 R이나 G이면
                if arr[dy][dx] != 'B' and arr[dy][dx] != 0: # R과 G는 같은 구역으로 본다
                    arr[dy][dx] = 0
                    q.append([dy,dx])

            elif arr[dy][dx] == tmp:
                arr[dy][dx] = 0
                q.append([dy,dx])

for j in range(N): # 일반인이 보는 구역 탐색
    for i in range(N):
        if arr[j][i] != 0:
            area += 1
            tmp = arr[j][i]
            bfs(j,i,tmp,0)

print(area)
area = 0 # 변수 초기화
arr = acc # arr을 초기배열로 초기화
for j in range(N): # 적록색약이 보는 구역 탐색
    for i in range(N):
        if arr[j][i] != 0:
            area += 1
            tmp = arr[j][i]
            bfs(j,i,tmp,1)
print(area)

• 2중포문으로 완전탐색을 하다가 섬을 만나게 되면 bfs를 이용하여 8방향으로 이어져있는 섬이라면 0으로 바꿔주면서 진행했다.

from collections import deque

while True:
    w,h = map(int,input().split())
    if w == 0 and h == 0: # 0,0이 입력되면 break
        break

    arr = [list(map(int,input().split())) for _ in range(h)]
    cnt = 0

    def bfs(j,i): # 인접한 섬을 전부 0 으로 바꿔주는 함수
        q = deque([(j,i)])

        directy = [-1,-1,-1,0,0,1,1,1]
        directx = [-1,0,1,-1,1,-1,0,1]

        while q:
            y,x = q.popleft()

            for k in range(8):
                dy = directy[k] + y
                dx = directx[k] + x

                if dy >= h or dy < 0 or dx >= w or dx < 0: # 배열 인덱스를 벗어난다면 continue
                    continue
                if arr[dy][dx] == 1:
                    arr[dy][dx] = 0
                    q.append([dy,dx])

    for j in range(h):
        for i in range(w):
            if arr[j][i] == 1: # 섬이 발견되면 본인을 0으로 만들고 bfs 함수 실행
                cnt += 1
                arr[j][i] = 0
                bfs(j,i)

    print(cnt)

• dfs 로 구현하려 했으나 파이썬 재귀제한에 걸려 재귀 제한을 넓혀주는 sys.setrecursionlimit(10000) 코드를 추가 했지만, 시간초과가 떠서 bfs로 구현하였다.
• bfs도 시간초과가 떠서 input 대신 sys.stdin.readline를 이용하였다.

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

V, E = map(int,input().split())
arr = [[0] * V for _ in range(V)]
used = [0]*V
cnt = 0

for i in range(E):
    y,x = map(int,input().split())

    arr[y-1][x-1] = 1
    arr[x-1][y-1] = 1

def bfs(now): # 연결 요소들을 bfs를 통해 다시 방문하지 않도록 해줌
    q = deque()
    q.append(now)

    while q:
        node = q.popleft()
        for i in range(V):
            if arr[node][i] == 1 and used[i] == 0:
                used[i] = 1
                q.append(i)

for j in range(V):
    flag = 0
    for i in range(V):
        if arr[j][i] == 1:
            flag = 1
            if used[j] == 0:
                used[j] = 1
                cnt += 1 # bfs가 실행될때마다 cnt + 1
                bfs(j)
    if flag == 0: # 연결 요소가 없는 정점이 없다면 카운트 추가
        cnt += 1

print(cnt)

• bfs, flood fill을 이용하여 시작점에서 끝점까지 이동할수 있는 칸을 지나며 +1을 해주고 끝 인덱스의 값을 출력하였다.

from collections import deque

N,M = map(int,input().split())
arr = [list(map(int,input())) for _ in range(N)]
used = [[0]*M for _ in range(N)] # used 배열을 통한 중복 접근 방지
directy = [-1,1,0,0]
directx = [0,0,-1,1]

def bfs(y,x):

    q = deque([(y,x)])
    while q:
        y,x = q.popleft()
        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열 범위를 벗어나면 continue
                continue
            if arr[dy][dx] == 1 and used[dy][dx] == 0: # 갈 수 있는 길이면서, 한번도 가지 않았던 곳이라면
                used[dy][dx] = 1 # used에 체크해주고
                arr[dy][dx] = arr[y][x] + arr[dy][dx] # 목표방향에 현재위치의 값을 더함
                q.append([dy,dx])

used[0][0] = 1 # 출발점의 used를 1로 바꾸고 bfs시작
bfs(0,0)
print(arr[-1][-1])

• dfs와 used를 통해 한번 들렀던 곳은 다시 들르지 않음으로써 dfs가 실행된 횟수만큼 카운트를 해주었다.

N = int(input())
M = int(input())

arr = [[0]*N for _ in range(N)]
used = [0] * N
cnt = 0

for i in range(M):
    y,x = map(int,input().split())

    arr[y-1][x-1] = 1
    arr[x-1][y-1] = 1

def dfs(now): # 1과 연결되어있는 정점의 수 만큼 cnt해줌
    global cnt

    for i in range(N):
        if arr[now][i] == 1 and used[i] == 0:
            used[i] = 1
            cnt += 1
            dfs(i)

used[0] = 1 # used배열, 자기 자신을 1로 만들고 dfs실행
dfs(0)
print(cnt)

• bfs를 통해 bfs함수를 실행할 떄 마다 카운트를 올리며(단지 수) bfs함수 내에서는 집을 카운트하며(집의 수) 0으로 바꾸는 작업을 진행하였다.

from collections import deque

N = int(input())

arr=[list(map(int,input())) for _ in range(N)]
cnt = 0 # 단지의 수
result = [] # 각 단지의 집의 수를 담을 리스트

def bfs(y,x):
    q = deque([(y,x)])
    tmp = 1 
    arr[y][x] = 0

    while q:
        y,x = q.popleft()

        directy = [-1,1,0,0] # 상,하,좌,우로만 이동
        directx = [0,0,-1,1] 

        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= N or dx < 0: # 목표 인덱스가 배열을 벗어난다면 continue
                continue
            if arr[dy][dx] == 1: 
                tmp += 1 # 상하좌우 내에 집이 있다면 임시변수에 +1
                arr[dy][dx] = 0
                q.append([dy,dx])
    result.append(tmp) # 단지의 집의 수를 result에 저장

for j in range(N):
    for i in range(N):
        if arr[j][i] == 1:
            cnt += 1 # 단지 수 카운트
            bfs(j,i)

print(cnt) # 단지 수 출력
result.sort()

for i in range(len(result)):
    print(result[i]) # 집의 수 출력

• bfs를 이용하여 구현하였다.

from collections import deque

N,M = map(int,input().split())
q = deque([(N,0)])
used = [0] * 100001

def bfs():
    while q:
        n,c = q.popleft()

        if 0 <= n <= 100000: # 동생의 최소, 최대 인덱스값을 벗어나지 않아야함
            if used[n] == 0: # used배열을 통해 왔던곳은 가지 않으며 시간 단축
                used[n] += 1
            else:
                continue
            if n == M:
                print(c)
                break
            q.append([n-1,c+1])
            q.append([n+1,c+1])
            q.append([n*2,c+1])

bfs()

• 배열 완전탐색을 통해 초기의 1의 인덱스값들을 저장 한 후 bfs를 통해 Max값을 구했다.
• bfs를 전부 돌고 난 후 완전탐색을 통해서 익지 않은 토마토가 있는 경우 (0)가 있다면 -1을 출력하도록 했다.

from collections import deque

M,N = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
used = [[0]*M for _ in range(N)]
q = deque()
Max = -21e8
for j in range(N):
    for i in range(M):
        if arr[j][i] == 1:
            q.append([j,i]) # 1의 인덱스값을 저장
            used[j][i] = 1

def bfs():
    global Max
    directy = [-1,1,0,0]
    directx = [0,0,-1,1]

    while q:
        y,x = q.popleft()
        if arr[y][x] > Max: 
            Max = arr[y][x] # bfs를 돌면서 Max값을 갱신

        for k in range(4):

            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어난다면 continue
                continue
            if arr[dy][dx] == -1: # 토마토가 들어 있지 않다면 continue
                continue
            if used[dy][dx] == 0:
                used[dy][dx] = 1
                arr[dy][dx] = arr[y][x] + 1 # 목표 인덱스를 자신의 +1
                q.append([dy,dx])


bfs()
flag = 0
for j in range(N):
    for i in range(M):
        if arr[j][i] == 0: # 배열을 돌며 익지않은 토마토가 있을 시 flag = 1
            flag = 1

if flag == 1:
    print("-1")
else:
    print(Max-1)

2중 for문으로 배열을 돌면서 1을 만나면, 카운트를 세며 bfs를 통해 인접한 모든 1을 0으로 만들어서 다시 접근 하지 않도록 하였다.

from collections import deque
TC = int(input())

for tc in range(1,TC+1):
    M,N,V = map(int,input().split())
    cnt = 0
    arr = [[0] * M for _ in range(N)]
    for i in range(V):
        x,y = map(int,input().split())
        arr[y][x] = 1

    def bfs(y,x):
    
        q = deque([(y,x)])
        
        while q:
            y,x = q.popleft()

            directy = [0,0,1,-1]
            directx = [1,-1,0,0]

            for k in range(4):
                dy = directy[k] + y
                dx = directx[k] + x

                if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열을 벗어난다면 continue
                    continue
                    
                if arr[dy][dx] == 1: # 인접한 배열중에 1이 있다면 0으로 바꿔줌
                    arr[dy][dx] = 0
                    q.append([dy,dx])

    for j in range(N):
        for i in range(M):
            if arr[j][i] == 1: # 1을 만난다면 cnt를 세주면서 본인을 0으로 바꿔주고 bfs 시작
                cnt += 1 
                arr[j][i] = 0
                bfs(j,i)

    print(cnt)