★BFS&DFS Advanced I - 13 Solved★

★ 7576 토마토 ★

 

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

M,N=map(int,input().split())
graph=[]
starts=[]
depths=[[0]*M for _ in range(N)]
visited=[[False]*M for _ in range(N)]

def BFS(graph, depths, starts, visited):
    queue = deque(starts)
    dx,dy=[0,0,-1,1],[-1,1,0,0]
    while queue:
        v = queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not visited[nx][ny] and graph[nx][ny] == 0:
                    graph[nx][ny] = 1
                    visited[nx][ny] = True
                    depths[nx][ny] = depths[v[0]][v[1]] + 1
                    queue.append((nx,ny))

for x1 in range(N):
    l=list(map(int,input().split()))
    graph.append(l)
    x2=0
    for y in l:
        if y == 1:
            starts.append((x1,x2))
            visited[x1][x2] = True
        x2+=1

BFS(graph, depths, starts, visited)

for x in range(N):
    for y in range(M):
        if graph[x][y] == 0:
            print(-1)
            sys.exit()

max_depth=-10_000_000
for x in range(N):
    max_depth=max(max_depth,max(depths[x]))
print(max_depth)

 

✴️ 상자 내에 익은 토마토들이 동시에 상하좌우 방향으로 이동하므로 실버 최단거리 기존 문제(시작점 1개)의 난이도 약간 상승. 시작점이 여러개인 BFS 최단거리 유형: 1일 때의 (x,y)를 starts list에 넣어 queue에 넣고 시작

 

✴️ 그 외) 0이 있다면 -1 출력하고 바로 종료 / 그게 아니라면 max 값 2차원 배열 돌려서 확인

---

★ 7569 토마토 ★

 

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

def BFS(graph, visited, depths, starts):
    queue = deque(starts)
    dx,dy,dz=[0,0,0,0,1,-1],[0,0,1,-1,0,0],[1,-1,0,0,0,0]
    while queue:
        v = queue.popleft()
        x,y,z=v[0],v[1],v[2]
        visited[x][y][z] = True
        for i in range(6):
            nx,ny,nz=x+dx[i],y+dy[i],z+dz[i]
            if 0<=nx<H and 0<=ny<N and 0<=nz<M:
                if visited[nx][ny][nz] == False and graph[nx][ny][nz] == 0:
                    queue.append((nx,ny,nz))
                    depths[nx][ny][nz] = depths[x][y][z] + 1
                    graph[nx][ny][nz] = 1 #riped

M,N,H=map(int,input().split())
graph=[[] for _ in range(H)]
starts=[]
for i in range(H):
    for j in range(N):
        l = list(map(int,input().split()))
        graph[i].append(l)
        for k in range(len(l)):
            if l[k] == 1:
                starts.append((i,j,k))

visited=[[[False]*M for _ in range(N)] for _ in range(H)]
depths=[[[0]*M for _ in range(N)] for _ in range(H)]

BFS(graph, visited, depths, starts)

for h in range(H):
    for x in range(N):
        for y in range(M):
            if graph[h][x][y] == 0:
                print(-1) #not all has ripened
                sys.exit()

max_depth=-2
for h in range(H):
    for x in range(N):
        max_depth=max(max_depth,max(depths[h][x]))
print(max_depth)

 

✴️ 높이 부분 상/하 방향으로도 쌓아야 한다는 점만 주의! 방향 벡터 dx, dy, dz = [0,0,0,0,-1,1], [0,0,-1,1,0,0], [-1,1,0,0,0,0] 이렇게 총 6가지의 방향벡터 존재

 

✴️ 시작점 동시에 진행 / depths BFS 최댓값 / 그 외 문제에 맞게 진행 (즉 나머지는 위의 7569 토마토 문제 풀이와 동일)

---

★ 14502 연구소 ★

 

import sys, copy
input=sys.stdin.readline
from collections import deque
from itertools import combinations

N,M=map(int,input().split())
graph_init=[]
virus=[]
pos=[]

def get_zero(graph, N, M, pos):
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                pos.append((i,j))
    return pos

def BFS(graph, virus, N, M, visited):
    queue=deque(virus)
    for v in virus:
        visited[v[0]][v[1]] = True
    dx,dy=[1,-1,0,0],[0,0,1,-1]
    while queue:
        v=queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not visited[nx][ny] and graph[nx][ny]==0:
                    visited[nx][ny]=True
                    graph[nx][ny] = 2
                    queue.append((nx,ny))

for x in range(N):
    l,y=list(map(int,input().split())),0
    graph_init.append(l)
    for i in l:
        if i == 2:
            virus.append((x,y))
        y+=1
pos=get_zero(graph_init,N,M,pos) #to find the potential spots to install a wall
ans=0

for pos_pair in combinations(pos,3):
    graph=copy.deepcopy(graph_init)
    for (x,y) in pos_pair:
        graph[x][y] = 1 #make a wall
    visited=[[False]*M for _ in range(N)]
    BFS(graph, virus, N, M, visited) #make virus spread
    areas=0
    for i in range(N):
        for j in range(M):
            if graph[i][j] == 0:
                areas+=1
    ans=max(ans,areas)
print(ans)

 

✴️

(1) 벽을 세울 수 있는 0 위치 pos list에 모으기

(2) virus 위치 모으기

(3) combinations(pos,3) 돌릴 때마다 brute-force로 매 case 안전영역의 크기 구해야 하므로 deepcopy() 계속 사용 → 세 군데 벽 세우고(1로 만들기) → 여러 virus 동시에 퍼지게 BFS 돌리기 → 0인 개수 areas로 구해서 ans update

---

★ 10026 적록색약 ★

 

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

N=int(input())
arr=[]
ans1,ans2=0,0

def BFS1(arr,visited,N,color,start):
    queue=deque([start])
    dx,dy=[0,0,1,-1],[1,-1,0,0]
    while queue:
        v=queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visited[nx][ny] == False and arr[nx][ny] == color:
                    visited[nx][ny]=True
                    queue.append((nx,ny))

def BFS2(arr,visited,N,color,start):
    queue=deque([start])
    dx,dy=[0,0,1,-1],[1,-1,0,0]
    while queue:
        v=queue.popleft()
        for i in range(4):
            nx,ny=v[0]+dx[i],v[1]+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visited[nx][ny] == False:
                    if color=='B':
                        if arr[nx][ny] == 'B':
                            visited[nx][ny]=True
                            queue.append((nx,ny))
                    else: #'R''G'
                        if arr[nx][ny] in ['R','G']:
                            visited[nx][ny]=True
                            queue.append((nx,ny))

for _ in range(N):
    arr.append(list(input().rstrip()))
visited1=[[False]*N for _ in range(N)]
visited2=[[False]*N for _ in range(N)]

for i in range(N):
    for j in range(N):
        color=arr[i][j]
        if not visited1[i][j]:
            visited1[i][j] = True
            BFS1(arr,visited1,N,color,(i,j))
            ans1+=1
        if not visited2[i][j]:
            visited2[i][j] = True
            BFS2(arr,visited2,N,color,(i,j))
            ans2+=1


print(ans1,ans2)

 

✴️ 적록색약이 아닐 경우 단순히 연결영역의 개수 + 적록색약일 경우 R/G/B if문 구분만 해주면 됨

---

★ 1240 노드 사이의 거리 ★

 

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

def BFS(tree, visited, x, y, d):
    visited[x]=True
    queue=deque([(x,0)])
    while queue:
        v,d=queue.popleft()
        if v == y:
            return d
        for sub_v in tree[v]:
            if not visited[sub_v[0]]:
                visited[sub_v[0]]=True
                queue.append((sub_v[0],sub_v[1]+d))

N,M=map(int,input().split())
tree=[[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,d=map(int,input().split())
    tree[a].append((b,d))
    tree[b].append((a,d))
for _ in range(M):
    x,y=map(int,input().split())
    visited=[False]*(N+1)
    print(BFS(tree,visited,x,y,0))

 

✴️ BFS의 depth 구하는 방식과 비슷하게 BFS의 주어진 두 노드 사이의 거리는 계속 update하면서 풀 수 있다.

 

✴️ 주어진 node의 (x,0) tuple을 queue로 돌리고((node 번호, 주어진 node에서 해당 node 번호까지의 거리)가 tuple 형태), 원하는 노드에 도달했다면(v==y) 바로 d 출력

 

※ BFS 사용 필요! BFS면 동시에 여러 방향으로 뻗치기 때문에 각 node에 원래 node로부터의 최단거리(즉, 간선 가중치의 합)이 저장되므로, queue로만 이동시킨다면 최종 node와 같을 때의 tuple 두번째 요소 바로 출력하면 끝! (최단거리 변형문제)

 

✴️ <최단거리와 다른 점> queue에 돌아가는 정보가 두 개 + BFS이므로 시작 node에서 시작되는 거리 누적(d)

---

★ 13913 숨바꼭질 4 ★

 

import sys
input=sys.stdin.readline
from collections import deque
N,K=map(int,input().split())
def BFS(visited, depths, start):
    visited[start] = True
    depths[start] = 0
    path[start] = 0
    queue = deque([start])

    while queue:
        next_node= queue.popleft()

        for child in [next_node-1, next_node+1, next_node*2]:
            if child == K:
                visited[child] = True
                print(depths[next_node]+1)
                path[child] = next_node
                return
            elif 0 <= child <= 100_000 and not visited[child]:
                visited[child] = True
                queue.append(child)
                depths[child] = depths[next_node] + 1
                path[child] = next_node
            else:
                pass

if N==K:
    print(0)
    print(K)
else:
    visited=[False]*(100_000+1)
    depths=[-1]*(100_000+1)
    path=[-1]*(100_000+1)
    start = N
    ans=[K]
    ind=K
    BFS(visited, depths, start)
    while path[ind]!=N:
        ans.append(path[ind])
        ind=path[ind]
    ans.append(N)
    print(*ans[::-1])

 

✴️ 가중치 우선순위 없는 BFS의 일반적인 최단경로 출력은 실버1 <1697 숨바꼭질> 문제. 여기서 최단경로의 모든노드 번호를 출력하는 최단경로 출력 기능이 추가

 

✴️ 아래 그림을 참조하듯, 자식 node를 index로하고 해당 자식 node의 list value로 부모 node를 저장. 그러면 도착 노드 K index부터 역으로 N index 만날 때 까지 출력하는 idea

: queue에 node가 들어갈 때 마다 path[child] = next_node로 path update. 예를 들어 5에서 17까지의 최단경로 내용 출력하고 싶다면 거꾸로 index 17부터 index 5를 만날 때까지 차례대로 역추적 경로 저장해 출력

---

★ 13549 숨바꼭질 3 ★

 

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

N,K=map(int,input().split())
depths=[-1]*(100_001)
visited=[False]*(100_001)

def BFS(depths, visited, N):
  queue = deque([N])
  visited[N] = True
  depths[N] = 0

  while queue:
    v = queue.popleft()

    if (2*v)<=100_000 and not visited[2*v]:
      visited[2*v] = True
      queue.append(2*v)
      depths[2*v] = depths[v]
      if (v*2) == K:
        return

    if 0<=(v-1) and not visited[(v-1)]:
      visited[v-1] = True
      queue.append(v-1)
      depths[v-1] = depths[v] + 1
      if (v-1) == K:
        return
  
    if (v+1)<=100_000 and not visited[(v+1)]:
      visited[v+1] = True
      queue.append(v+1)
      depths[v+1] = depths[v] + 1
      if (v+1) == K:
        return

    
  

if N==K:
  print(0)
else:
  BFS(depths, visited, N)
  print(depths[K])

 

✴️ 실버1 1697 숨바꼭질 문제와 유사

 

→ 하지만 위 문제는 0초 후에 2*X로 이동한다는 점. 즉 X-1이나 X+1 이동보다 2*X를 먼저 고려(가중치 우선순위가 있는 BFS 변형)해야 한다. 따라서 v*2가 K인지 아닌 지를 다른 케이스 X-1 / X+1 이동보다 먼저 따져야 함. queue에서 가장 먼저 2*X로 이동한 경우가 대기해야 후순위인 X-1이나 X+1로 이동했을 때 나온 최단시간보다 더 최단시간이 나와도 먼저 잡아서 출력할 수 있기 때문

---

★ 16928 뱀과 사다리 게임 ★

 

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

N,M=map(int,input().split())
depths=[-1]*101
visited=[False]*101
d=[1,2,3,4,5,6]
snake_ladder=dict() #no snake/ladder exists in 1 and 100

def BFS(depths, visited, start):
    visited[start] = True
    depths[start] = 0
    queue=deque([start])
    while queue:
        v = queue.popleft()
        for i in range(6):
            nx=v+d[i]
            if nx<=100 and not visited[nx]:
                depths[nx] = depths[v] + 1
                visited[nx] = True
                if nx==100: #arrived at destination   
                    return
                if nx not in snake_ladder.keys(): # not arrived in snake / ladder
                    queue.append(nx)
                else: #arrived in snake/ladder
                    after=snake_ladder[nx]
                    if not visited[after]:
                        visited[after] = True 
                        depths[after] = depths[nx]
                        queue.append(after)

for _ in range(N):
    x,y=map(int,input().split())
    snake_ladder[x]=y
for _ in range(M):
    u,v=map(int,input().split())
    snake_ladder[u]=v

BFS(depths,visited,1)

print(depths[100])

 

✴️ 최단거리 구하기 BFS depth 전형적인 유형에, 뱀과 사다리를 활용해 다른 node에서 다른 node로 이동이 가능한 기능만 추가됨

 

✴️ dict()를 만들어 snake나 ladder일 경우 이후 이동되는 node가 not visited일 경우 depth 변화 없이 할당 / 이후 이동되는 node 방문 처리 / queue에 이후 이동되는 node 넣기 3개만 처리하면 바로 끝!

 

★ BFS이고 시작점이 정해져있으므로 도착점을 향해 동시에 방향이 있는 상태로 진행하기 때문에 도중에 뱀이나 사다리로 node를 이동해도 visited 처리만 잘 한다면 끝점까지 최단거리를 BFS depth로 바로 구할 수 있다.

---

★ 9019 DSLR ★

 

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

def BFS(visited,start,end):
    visited[start[0]]=True
    queue=deque([start])
    while queue:
        v=queue.popleft()
        #D
        D=(2*v[0])%10000
        #S
        S=(v[0]-1) if (v[0]-1)>=0 else 9999
        #L
        l=str(v[0]).zfill(4)
        L=int(l[1]+l[2]+l[3]+l[0])
        #R
        r=str(v[0]).zfill(4)
        R=int(r[3]+r[0]+r[1]+r[2])

        DSLR=[D,S,L,R]

        for nv in range(len(DSLR)):
            if not visited[DSLR[nv]]:
                visited[DSLR[nv]]=True
                if DSLR[nv] == end: #if answer found
                    return v[1]+['DSLR'[nv]]
                queue.append([DSLR[nv],v[1]+['DSLR'[nv]]])


for _ in range(int(input())):
    A,B=map(int,input().split())
    visited=[False]*(10_000)
    depths=[-1]*(10_000)

    print(*BFS(visited,[A,[]],B),sep='')

 

✴️ 위 BOJ 1240 노드 사이의 거리와 마찬가지로 queue에 넣을 때, 노드 번호 + 해당 노드까지의 DSLR 조합 명령어를 넣는다는 BFS 최단거리 응용문제. BFS traversing하면서 두 번째 정보 문자열이 계속 더해짐만 보면 됨. queue에 두 가지 정보가 들어감을 인지하기만 하면 OK!

---

★ 1963 소수 경로 ★

 

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

def BFS(start,end):
    dq=deque([(start,0)])
    while dq:
        n,depth=dq.popleft()
        if not visited[n]:
            visited[n] = True
            for i in range(4):
                for j in range(10):
                    if i == 0:
                        if j != 0:
                            next_n = int(str(j)+str(n)[1:])
                        else: continue
                    else:
                        next_n = int(str(n)[:i]+str(j)+str(n)[i+1:])
                    if next_n == end:
                            return depth + 1
                    else:
                        if not visited[next_n] and sieve[next_n]:
                            dq.append((next_n,depth+1))
    return 'Impossible'


#sieve ~9999
sieve = [True]*(10001)
sieve[0],sieve[1]=False,False

for i in range(2,10001):
    if sieve[i] == True:
        for j in range(i,10001,i):
            sieve[j] = False
        sieve[i] = True


for _ in range(int(input())):
    x,y=map(int,input().split())
    visited=[False]*10001
    if x == y:
        print(0)
    else:
        print(BFS(x,y))

 

✴️ x → y로 가는 소수의 경로를 BFS로 찾는다. x의 각 자리를 brute-force로 0부터 9까지 바꾸며(첫 자리만 0 제외) 만든 next_n이 소수에 해당되고 not visited라면 BFS deque에 (next_n, depth + 1) append. (네 자리까지 소수 sieve 에라토스테네스 체로 미리 생성)

 

※ 이 때 not visited 점검 이유는, 이미 방문했다면 방문한 숫자의 depth가 현재 depth보다 작거나 같으므로 해당 next_n 이후를 점검할 필요 x

---

★ 12851 숨바꼭질 2 ★

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

def BFS(visited, depths, start, cnt):
    visited[start] = True
    depths[start] = 0
    queue = deque([start])
    found=False

    while queue:
        v = queue.popleft()
        for child in [v-1, v+1, v*2]:
            if 0 <= child <= 100_000: #cond1
                if child == K:
                    if not found:
                        depths[child] = depths[v] + 1
                        found = True
                        found_depth = depths[child]
                        visited[child] = True
                        cnt+=1
                    else: #found again
                        if found_depth == depths[v] + 1:
                            cnt+=1
                        else:
                            return cnt
                else: #child!=K
                    if not visited[child]:
                        depths[child] = depths[v] + 1
                        visited[child] = True
                        queue.append(child)
                        if found:
                            if found_depth < depths[child]:
                                return cnt
                    else: #visited[child] = True
                        if depths[child] == depths[v] + 1:
                            depths[child] = depths[v] + 1
                            visited[child] = True
                            queue.append(child)
                            if found:
                                if found_depth < depths[child]:
                                    return cnt
    return cnt



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

if N==K:
    print(0,1,sep='\n')
else:
    visited=[False]*(100_000+1)
    depths=[-1]*(100_000+1)
    start = N
    cnt = 0
    x = BFS(visited, depths, start, cnt)
    print(depths[K], x, sep='\n')

 

✴️ 위 그래프 1 → 6을 가기 위한 BFS 그림 예시 참조. 최단거리 가짓수는 flag 변수 활용 & depth 부등식 활용으로 풀 수 있다.

 

(1) 주어진 숫자 범위 아닌 child node 제외(노란색 X)

 

(2) ex) 현재 node에서 v-1, v+1, 2*v로 뻗었을 때(BFS 탐색)

① child node가 목표 node가 아닌 경우

[1] child node를 방문하지 않은 새로운 node (위 그림 보라색) : depths update, visited True 설정, queue에 넣기

 

[2] child node를 이미 방문한 node(ex 위의 그림의 경우 depth 1에서 2로 뻗을 때 node number 2) (위 그림 초록색) : 동일한 number의 node는 동일 depth에 있을 때만 이후 탐색 가능하고, 이미 이전 depth에 존재한다면 pass

→ 따라서 depths[child] == depths[v] + 1일 경우만 depths update, queue에 넣기

 

② child node가 목표 node인 경우

[1] 첫 목표 node 도달이라면(found == False) (위 그림 빨간색): depths update, visited True 설정, queue에 넣기, found = True, found_depth 설정, cnt(정답변수) += 1

 

[2] 이미 도달한 적이 있다면 (위 그림 노란색): found_depth == depths[v] + 1일 경우만 cnt += 1

 

+ return 종료 코드 넣기 +

 

① child node가 목표 node가 아닌 경우

[1] child node를 방문하지 않은 새로운 node인 경우(위 그림 보라색)

: if found 답 찾았다면 → found_depth보다 현재 depth[child]가 더 크다면, return 종료(그 다음 depth로 진행된 것이므로)

 

[2] child node를 이미 방문한 node인 경우(위 그림 초록색)

: 동일한 number의 node가 동일 depth에 있을 경우 → if found 답 찾았다면 → found_depth보다 현재 depth[child]가 더 크다면, return 종료(그 다음 depth로 진행된 것이므로)

 

② child node가 목표 node인 경우

[1] 처음으로 도달(위 그림 빨간색)

: return x

 

[2] 이미 도달한 적 있는 경우(위 그림 노란색)

: 이미 찾은 found_depth와 현재 depth(depths[v]+1)와 서로 같지 않다면, return 종료

 

※ 최단경로 갯수 핵심은, found bool flag 변수를 만든 뒤,

처음으로 도달하지 않은 경우(found==True)일 때 처음으로 도달했을 때의 node depth(found_depth)와 현재 depth를 비교. 즉 depth를 비교하면서 최단경로 갯수를 update하면 된다. 그리고 현재 depth가 found_depth를 넘어섰으면 return 종료 ※

---

★ 3055 탈출 ★

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

R,C=map(int,input().split())

def spread_water(waters):
    dx,dy = [-1,1,0,0], [0,0,-1,1]
    lw = len(waters)
    cnt = 0
    while cnt<lw:
        water = waters.popleft()
        x,y = water[0],water[1]
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<R and 0<=ny<C:
                if graph[nx][ny] == '.':
                    graph[nx][ny] = '*'
                    waters.append((nx,ny))
        cnt+=1


def BFS(graph, visited, waters, start, depths):
    queue = deque([start])
    visited[start[0]][start[1]] = True
    dx,dy = [-1,1,0,0], [0,0,-1,1]
    prev_depth = 0
    while queue:
        node = queue.popleft()
        x,y=node[0],node[1]
        for i in range(4):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<R and 0<=ny<C:
                if graph[nx][ny] in ['D', '.'] and not visited[nx][ny]:
                    if prev_depth != depths[x][y] + 1:
                        spread_water(waters)
                if graph[nx][ny] == 'D':
                    print(depths[x][y]+1)
                    sys.exit()
                if graph[nx][ny] == '.' and not visited[nx][ny]:
                    visited[nx][ny] = True
                    depths[nx][ny] = depths[x][y] + 1
                    prev_depth = depths[nx][ny]
                    queue.append((nx,ny))



graph=[]
waters = deque()
visited = [[False]*C for _ in range(R)]
depths = [[-1]*C for _ in range(R)]
for i in range(R):
    x = list(input().rstrip())
    for j in range(C):
        if x[j] == 'D':
            gul = (i,j)
        elif x[j] == 'S':
            start = (i,j)
            depths[i][j] = 0
        elif x[j] == '*':
            waters.append((i,j))
    graph.append(x)

second = 0
BFS(graph, visited, waters, start, depths)
print('KAKTUS')

 

✴️ 고슴도치가 S부터 시작해서 이동하기 전, 물이 퍼지는 알고리즘 실행. 이 때 depth가 달라질 때만 이동하기 전 물이 퍼지는 알고리즘 실행.

 

✴️ 물이 퍼지는 BFS 알고리즘: 주어진 물 개수만큼만 queue 돌리면서 BFS

 

✴️ 시작 지점을 depth 0으로 하고 목적지까지 가는 거리가 소요시간과 동일한 개념이므로 목적지에서의 depth 출력 / depth 출력을 못하면 KAKTUS 출력

---

★ 14395 4연산 ★

import sys
input=sys.stdin.readline
from collections import deque
s,t=map(int,input().split())

def BFS(queue,visited,start,end):
    global found
    found = False
    while queue:
        v = queue.popleft()
        for op in ['*','+','-','/']:
            if op=='*':
                if v[0]*v[0] == t:
                    found=True
                    v[1]+='*'
                    print(*v[1],sep='')
                    return
                if v[0]*v[0] not in visited and v[0]*v[0]<=10**9:
                    visited.add(v[0]*v[0])
                    new_v=v[1]+'*'
                    queue.append([v[0]*v[0],new_v])
            elif op=='+':
                if (v[0]+v[0]) == t:
                    found=True
                    v[1]+='+'
                    print(*v[1],sep='')
                    return
                if (v[0]+v[0]) not in visited and (v[0]+v[0])<=10**9:
                    visited.add(v[0]+v[0])
                    new_v=v[1]+'+'
                    queue.append([v[0]+v[0],new_v])
            elif op=='-':
                if (v[0]-v[0]) == t:
                    found=True
                    v[1]+='-'
                    print(*v[1],sep='')
                    return
                if (v[0]-v[0]) not in visited and 0<=(v[0]-v[0]):
                    visited.add(v[0]-v[0])
                    new_v=v[1]+'-'
                    queue.append([v[0]-v[0],new_v])
            else:
                if v[0]!=0:
                    if (v[0]//v[0])==t:
                        found=True
                        v[1]+='/'
                        print(*v[1],sep='')
                        return
                    if (v[0]//v[0]) not in visited and 1<=(v[0]//v[0]):
                        visited.add(v[0]//v[0])
                        new_v=v[1]+'/'
                        queue.append([v[0]//v[0],new_v])



if s==t: print(0)
else:
    visited=set()
    visited.add(s)
    queue=deque([[s,'']])
    BFS(queue,visited,s,t)
    if not found:
        print(-1)

 

✴️ queue 자료구조를 활용해 먼저 넣은 것 먼저 빼서 * + - / 순서로 연산 진행. 최소 연산의 횟수를 구하므로, queue 자료구조를 활용해 먼저 뺀 것을(popleft()) 연산 진행해야 greedy한 관점에서 최소 연산 횟수를 구할 수 있다.

 

✴️ visited 배열을 전체 수의 크기 10^9까지 만들기에는 메모리 초과 발생. set를 활용해 bfs 과정 중 만들어진 숫자만 visited set 자료구조에 넣어 방문 여부 체크(set의 in O(1)). 방문했다면 더 이상 bfs 진행할 필요 x. 이미 앞선 순서에서 +, -,*, /의 케이스 각각을 살펴보았으므로 동ㅇ일하게 한 번 더 +, -, *, /를 체킹할 필요는 없다.

 

✴️ queue 자체에 넣는 노드는 바뀌는 숫자와 업데이트 되는 연산의 순서 이렇게 2개를 list로 만들어 진행시키면 된다.

---