★BFS&DFS Advanced I - 10 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 토마토 ★ (3차원 최단경로) 

 

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 = [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

---