문제 : https://www.acmicpc.net/problem/7576

▶ 서로 다른 여러점에서, 동시에 물들여서 며칠이 걸리는지 알아내는 문제 

▶ 코드 ( 큐 ver. )

# 예외처리가 중요
# 예외1)) 다 물들였는데, 0 남아있는 경우 : -1 출력
# 예외2)) 애초에 0원소가 없는경우 : 0 출력 


from collections import deque

m,n = map(int, input().split()) # m: 가로, n: 세로
myMap = []
ripe = deque() # 익은 토마토 위치 

for i in range(n):
    row = list(map(int, input().split()))
    for j in range(m):
        if row[j] == 1:
            ripe.append([i,j])
    myMap.append(row)
#print(myMap)
#print(ripe) # deque([[0, 0], [3, 5]])

dx = [1,-1,0,0]
dy = [0,0,1,-1]

#visited = [[0]*m for _ in range(n)] # 필요 X

def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs():
    
    days = -1

    while ripe:
        days += 1
        for _ in range(len(ripe)):  # 현재 ripe의 원소 개수만큼만 반복 !! ★
            x, y = ripe.popleft()   # [0,0], [3,5] 까지만  

            tx = 0
            ty = 0
            for i in range(4):
                tx = x + dx[i]
                ty = y + dy[i]

                if isInGraph(tx, ty):
                    if myMap[tx][ty] == 0: # [tx, ty] not in ripe 조건 추가하면 시간초과
                        myMap[tx][ty] = 1
                        ripe.append([tx,ty])

    # 예외1)) 
    for row in myMap:
        if 0 in row:
            return -1
    return days
        

print( bfs() )
#print(myMap)

#참조: https://dojinkimm.github.io/problem_solving/2019/11/03/boj-7576-tomato.html

※ python3로 채점해야 메모리초과 X

※ 방문한 myMap의 원소를 0 -> 1로 바꿔주므로, visited를 통한 방문처리 필요 X

※ [tx, ty] not in ripe 조건 추가하면 시간초과

문제 : https://www.acmicpc.net/problem/2178

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 안해서 시간초과

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

▶ 코드 ( 큐 ver. )

■큐에 중복 원소(r, l)이 있는지 검사 추가. 정답

from collections import deque

n, m = map(int, input().split()) # n:세로, m:가로
myMap = []

for _ in range(n):
    inputString = input()
    myMap.append(list(map(int, inputString)))
#print(myMap)
    
dx = [1,-1,0,0]
dy = [0,0,1,-1]

visited = [[0]*m for _ in range(n)]
depth = [[0]*m for _ in range(n)]
    
def isInGraph(r, l): # r: 세로, l: 가로
    if r < 0 or r >= n or l < 0 or l >= m:
        return False
    return True
    
def bfs(r, l):
    
    visited[r][l] = 1
    depth[r][l] = 1 # 처음 시작은 1

    # 큐 이용
    dq = deque()
    dq.append([r,l]) # BFS로 사용될 큐 

    while dq:
        [r, l] = dq.popleft()
        visited[r][l] = 1
    
        #상하좌우 탐색
        tx = 0
        tx = 0
        for i in range(4):
              tx = r + dx[i]
              ty = l + dy[i]

              if isInGraph(tx, ty):
                  if visited[tx][ty] == 0 and myMap[tx][ty] == 1 and [tx,ty] not in dq:
                      dq.append([tx,ty])
                      depth[tx][ty] = depth[r][l] + 1

    
        '''
        # 재귀 이용 
        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and myMap[tx][ty] == 1:
                bfs(tx, ty, depth_list[r][l]+1)
        '''

bfs(0,0) # 첫위치 에서 시작 

print(depth[n-1][m-1])

※ python3로 채점해야 메모리초과 X

※ 원배열이 모두 1이므로, visited를 통해 방문처리 해줘야 한다.

※ 큐에서 뺀 원소가 큐에 있는지 검사 추가 해줘야 시간초과 X 되는 문제 

문제 : https://www.acmicpc.net/problem/1012 

▶ 코드 ( 재귀 ver. )

import sys
sys.setrecursionlimit(10**8) # 10^8 까지 늘림.


T = int(input())

for _ in range(T):
    m, n, k = map(int, input().split())
    myMap = [[0]*m for _ in range(n)]
    for _ in range(k):
        a, b = map(int, input().split())
        myMap[b][a] = 1

    #print(myMap)
    visited = [[0]*m for _ in range(n)]

    dx = [1,-1,0,0]
    dy = [0,0,1,-1]
        

    def isInGraph(r, l): # r: 세로, l: 가로
        if r < 0 or r >= n or l < 0 or l >= m:
            return False
        return True
        
    def bfs(r, l):
        visited[r][l] = 1

        tx = 0
        ty = 0
        for i in range(4):
            tx = r + dx[i]
            ty = l + dy[i]

            if isInGraph(tx, ty):
                if visited[tx][ty] == 0 and myMap[tx][ty] == myMap[r][l]:
                    bfs(tx, ty)

    ans = 0
    for i in range(n): # 세로길이
        for j in range(m): # 가로길이 
            if visited[i][j] == 0 and myMap[i][j] != 0:
                bfs(i, j)
                ans += 1
    print(ans)


# pypy로 제출하면 메모리초과. python3로 제출해야됨 

※ python3로 채점해야 메모리초과 X

문제 : https://www.acmicpc.net/problem/2667

▶ 코드( 재귀 ver. )

n = int(input())

m = []

for _ in range(n):
    num = str(input())
    num = list(map(int, num))
    m.append(num)
#print(m)

visited = [[0]*n for i in range(n)]

dx = [1,-1,0,0]
dy = [0,0,1,-1]

def isInGraph(r, l):
    if r < 0 or r >= n or l < 0 or l >= n:
        return False
    return True
    
def bfs(r, l):
    visited[r][l] = 1
    cnt = 1

    tx = 0
    ty = 0
    for i in range(4):
        tx = r + dx[i]
        ty = l + dy[i]

        if isInGraph(tx, ty):
            if visited[tx][ty] == 0 and m[tx][ty] == m[r][l]:
                cnt += bfs(tx, ty)
    return cnt
            
            
    
ans = []

for i in range(n):
    for j in range(n):
        if visited[i][j] == 0 and m[i][j] != 0:
            ans.append(bfs(i, j))
ans.sort()
print(len(ans))
for a in ans:
    print(a)

문제 : https://www.acmicpc.net/problem/2606

▶ 코드 ( 큐 ver. )

from collections import deque

n = int(input())
m = int(input())

s = [[0]*(n+1) for i in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    s[a][b] = 1
    s[b][a] = 1

def bfs(v):
    dq = deque([v])
    visited[v] = 1
    c = 0
    
    while(dq):
        v = dq.popleft()
        for i in range(1, n+1):
            if visited[i] == 0 and s[v][i] == 1:
                dq.append(i)
                visited[i] = 1
                c += 1
    print(c)


bfs(1)
    

문제 : https://www.acmicpc.net/problem/1260

▶ 코드 ( 큐 ver. )

from collections import deque

n, m, v = map(int, input().split())

s = [[0]*(n+1) for i in range(n+1)]
visited = [0]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    s[a][b] = 1
    s[b][a] = 1



def dfs(v):
    print(v, end=' ')
    visited[v] = 1
    for i in range(1, n+1):
        if visited[i] == 0 and s[v][i] == 1:
            dfs(i)

def bfs(v):
    dq = deque([v])
    visited[v] = 1
    while(dq):
        v = dq.popleft()
        print(v, end=' ')
        for i in range(1, n+1):
            if visited[i] == 0 and s[v][i] == 1:
                dq.append(i)
                visited[i] = 1
        



dfs(v)
print()
visited = [0]*(n+1) # visited 초기화 
bfs(v)