★BFS&DFS Intermediate I - 17 Solved★

 

DFS / BFS

🙆‍♂️ 그래프로 표현되는 여러 상황에서, 각 node의 visited 유무를 따질 때 그래프 탐색 방법에 따라 DFS / BFS로 나뉨

 

🙆‍♂️ 깊이있게 먼저 탐색하자면 DFS / 가까운 것 먼저 탐색하자면 BFS

 

🙆‍♂️ DFS / BFS 모두 딱! 3가지의 준비물 필요

 

※ 이 때 DFS는 stack 사용 / BFS는 queue를 사용하므로 BFS 사용 시 deque import ※

 

① 2차원 graph (각 node별로 연결된 node의 번호가 list로 저장됨)

② visited 여부 1차원 list (최종적으로 방문되었는 지 확인)

③ 시작 node

---

★ 1260 DFS와 BFS ★

 

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

def DFS(graph,v,visited):
    visited[v] = True
    print(v, end = ' ')
    for i in graph[v]:
        if not visited[i]:
            DFS(graph,i,visited)

def BFS(graph,start,visited):
    queue = deque([start])

    visited[start] = True

    while queue:
        v = queue.popleft()
        print(v,end= ' ')

        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

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

#graph 초기화
graph = [ [] for i in range(N+1)]

#graph 완성
for _ in range(M):
    a,b = map(int,input().split())

    graph[a].append(b)
    graph[b].append(a)

for i in range(N+1):
    graph[i].sort()

visited=[False]*(N+1)
DFS(graph,V,visited)
print()
visited=[False]*(N+1)
BFS(graph,V,visited)

 

🙆‍♂️ 전형적인 dfs/bfs 문제

 

🙆‍♂️ 다만, 방문 시 번호가 큰 node부터 먼저 방문하므로 만든 graph를 sorting한 다음 탐색 시작

---

★ 2606 바이러스 ★

 

import sys
input=sys.stdin.readline

def dfs(graph,n,visited):
    visited[n] = True #visited
    for i in graph[n]:
        if not visited[i]:
            dfs(graph,i,visited)

N=int(input())

graph=[[] for _ in range(N+1)]

for _ in range(int(input())):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

visited=[False]*(N+1)

dfs(graph,1,visited)
print(sum(visited)-1)

 

🙆‍♂️ 바이러스가 한 번 감염되면, 인접한 노드까지 모두 감염되므로, 감염되는 컴퓨터의 개수를 세는 매우 전형적인 graph 문제

 

🙆‍♂️ 인접한 부분까지 감염되는, 그래프 idea를 떠올려야 함. BFS 유형으로 해결했다.

 

🙆‍♂️ 먼저 2차원 그래프 초기화 뒤 그래프를 만들고, visited list와 시작 노드 1부터 dfs 함수를 거쳐 update된 visited의 True 개수 반환 (1 제외)

---

★ 24479 알고리즘 수업 - 깊이 우선 탐색 1 ★

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

global n
n = 0

def dfs(graph,start,orders):
    global n
    n+=1
    orders[start]=n

    for node in sorted(graph[start]):
        if orders[node] == 0: #if not visited
            dfs(graph,node,orders)


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

#graph
graph=[[] for _ in range(N+1)]

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

#orders
orders=[0]*(N+1)

#dfs
dfs(graph,R,orders)

print(*orders[1:],sep='\n')

 

🙆‍♂️ 전형적인 DFS 문제이나, 한 노드에서 여러 연결된 노드를 방문 시 작은 수부터 먼저 방문해야 한다는 규칙이 추가된 DFS

 

🙆‍♂️ 따라서, pseudo-code에 맞게 그대로 for node in sorted(graph[start])를 시작

 

🙆‍♂️ dfs 세 가지 준비물

① 2차원 그래프 (양 방향별로 모두 준비 - 두 번 append)

② 시작 start R

③ 각 노드 번호별 방문순서를 저장한 1차원 list

 

🙆‍♂️ dfs()를 들어가면

① 먼저 방문했으므로 방문표시(순서 전역변수 n 1 증가 / 방문순서 list에 순서 n 삽입)

② 인근 node들 sorted()한 상태에서 만약 방문 안했으면, 차례대로 dfs()

 

🙆‍♂️ 각 노드별로 방문순서를 알아봐야 하고, 오름차순으로 노드를 방문한다는 규칙이 들어간 변형된 dfs 유형!

---

★ 24480 알고리즘 수업 - 깊이 우선 탐색 2 ★

 

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)

global n
n = 0

def dfs(graph,start,orders):
    global n
    n+=1
    orders[start]=n

    for node in sorted(graph[start],reverse=True):
        if orders[node] == 0: #if not visited
            dfs(graph,node,orders)


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

#graph
graph=[[] for _ in range(N+1)]

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

#orders
orders=[0]*(N+1)

#dfs
dfs(graph,R,orders)

print(*orders[1:],sep='\n')

 

🙆‍♂️ 위 24479와 완전 똑같은 문제. 방문순서만 거꾸로. reverse=True

---

★ 24444 알고리즘 수업 - 너비 우선 탐색 1 ★

 

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

def BFS(graph,visited,orders,start):
    queue = deque([start])
    visited[start] = True
    order = 1
    orders[start] = order 
    while queue:
        next_node = queue.popleft()
        for i in graph[next_node]:
            if visited[i] == False:
                order+=1
                orders[i] = order
                queue.append(i)
                visited[i] = True



N,M,R=map(int,input().split())
graph=[[] for _ in range(N+1)]
visited=[False]*(N+1)
orders=[0]*(N+1)

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in graph:
    i.sort()

BFS(graph,visited,orders,R)

print(*orders[1:],sep='\n')

 

🙆‍♂️ 크게 2가지만 주의하면 된다!

 

(1) 그래프 만들 때 애초에 sort()로 노드 번호가 오름차순 정렬

(2) 방문 순서를 출력해야 하므로 별도의 orders[] 배열 만들고 초기값 order가 1씩 증가하게끔 node값 설정

 

🙆‍♂️ BFS 함수 틀 다시 보면

① 먼저 start node (1) visited 방문 처리 + (2) queue 만들고 넣기

② queue가 존재하는 동안 (1) popleft() 꺼내고 + (2) for문으로 각각의 node를 돌려 방문 안했으면 visited 방문 처리 + queue에 넣기

 

③ 위 문제는 특정적으로 추가로 '방문순서' 배열을 한 번 더 넣어서 방문안했으면 방문처리할 때 1씩 증가한 order를 넣기

---

★ 24445 알고리즘 수업 - 너비 우선 탐색 2 ★

 

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

def BFS(graph,visited,orders,start):
    queue = deque([start])
    visited[start] = True
    order = 1
    orders[start] = order 
    while queue:
        next_node = queue.popleft()
        for i in graph[next_node]:
            if visited[i] == False:
                order+=1
                orders[i] = order
                queue.append(i)
                visited[i] = True



N,M,R=map(int,input().split())
graph=[[] for _ in range(N+1)]
visited=[False]*(N+1)
orders=[0]*(N+1)

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for i in graph:
    i.sort(reverse=True)

BFS(graph,visited,orders,R)

print(*orders[1:],sep='\n')

 

🙆‍♂️ 위 24444번 문제와 똑같되 내림차순 문제이다!

---

★ 24446 알고리즘 수업 - 너비 우선 탐색 3 ★

 

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

def BFS(graph,visited,depths,start):
    queue = deque([start])
    visited[start] = True
    depths[start] = 0
    while queue:
        next_node = queue.popleft()
        for i in graph[next_node]:
            if visited[i] == False:
                depths[i] = depths[next_node]+1
                queue.append(i)
                visited[i] = True

N,M,R=map(int,input().split())
graph=[[] for _ in range(N+1)]
visited=[False]*(N+1)
depths=[-1]*(N+1)

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

BFS(graph,visited,depths,R)

print(*depths[1:],sep='\n')

 

☝️ 전형적인 BFS 문제에서 BFS의 깊이를 추가로 구하는 유형!

 

☝️ BFS의 깊이를 구하고 싶다면 BFS에서 원래 쓰이는 visited list 외에 depths라는 list를 추가로 사용!

 

☝️ 위 코드 일부에서 next_node로부터 나온 자식 node인 i의 depth는 당연히 위 부모 node의 깊이보다 1크므로 visited값이 False인 경우, 방문 카운트되는 노드에 한해서 이미 방문한 부모노드의 깊이보다 1 증가한 값을 기존 depths list에 넣는다. (유형 풀이 반드시 기억!)

 

☝️ 이후 최종적으로 depth list 값 출력하면 끝! 이 때, list의 index는 0부터 시작하므로 1번 노드부터이기에 index 혼동 조심

---

★ 24447 알고리즘 수업 - 너비 우선 탐색 4 ★

 

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


def BFS(graph, visited, depths, orders, start):
    #initialization (first node in a queue)
    queue = deque([start])
    visited[start] = True
    depths[start] = 0
    cur_order = 1
    orders[start] = cur_order

    while queue:
        next_node = queue.popleft()
        for child_node in graph[next_node]:
            if visited[child_node] == False: #if not visited(child node)
                visited[child_node] = True #visited
                queue.append(child_node) #enqueue
                depths[child_node] = depths[next_node] + 1
                cur_order += 1
                orders[child_node] = cur_order

N,M,R=map(int,input().split())
graph=[[] for _ in range(N+1)]
visited=[False]*(N+1)
depths=[-1]*(N+1)
orders=[0]*(N+1)
ans = 0

for _ in range(M):
    u,v=map(int,input().split())
    graph[u].append(v)
    graph[v].append(u)

for nodes in graph:
    nodes.sort()

BFS(graph, visited, depths, orders, R)

for d, t in zip(depths[1:], orders[1:]):
    ans += (d*t)

print(ans)

 

☝️ 너비우선탐색에서의 노드 방문 순서 + 노드 깊이 두 개의 곱합을 출력하는 유형!

---

《최단경로》 ★ 16953 A → B ★

 

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

A,B=map(int,input().split())

queue=deque([A])
cnt=0
limit=1
bf=0
while queue:
    cnt+=1
    bf=0
    for _ in range(limit):
        n = queue.popleft()
        if (n*2) == B:
            print(cnt+1)
            sys.exit()
        elif int(str(n)+'1') == B:
            print(cnt+1)
            sys.exit()
        else:
            if (n*2)<B:
                queue.append(n*2)
                bf+=1
            if (int(str(n)+'1'))<B:
                queue.append(int(str(n)+'1'))
                bf+=1
    limit=bf


print(-1)

 

 

☝️ BFS 아이디어임을 알아차리는 것이 무엇보다도 중요. 이 때 지속적으로 *2 또는 뒤에 1을 붙인 결과가 B보다 크다면 queue에 넣으면서 bf 변수 누적으로 더해지며 limit update. (즉 B보다 크지 않다면 enqueue 안하고 bf count 제외) limit에 다다르면 cnt+=1

 

☝️ 도중에 B 나오면 cnt+1 (문제에 최솟값 + 1이라 했으므로) 출력하고 sys.exit()

 

☝️ 그렇지 않으면, 즉 모든 queue 다 진행되어도 없다면 -1 출력

 

★ 하지만.....! BFS의 depth로 한번에 구하는게 속 편함 ☝️

---

《최단경로》 ★ 2644 촌수계산 ★

 

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

n=int(input())
graph=[[] for _ in range(n+1)]

def BFS(graph, visited, chon, start):
  queue = deque([start])
  visited[start] = True

  while queue:
    node = queue.popleft()
    for v in graph[node]:
      if not visited[v]:
        chon[v] = chon[node] + 1
        visited[v] = True
        queue.append(v)

x,y=map(int,input().split())
m=int(input())

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

visited=[False]*(n+1)
chon=[0]*(n+1)

BFS(graph, visited, chon, x)

if chon[y] == 0:
  print(-1)
else:
  print(chon[y])

 

☝️ x,y 중 한 명을 시작점으로 지정하고 전체 BFS의 depth를 계산한 뒤, y의 depth 값 구하면 끝!

 

☝️ BFS의 depth 계산 유형 - 특정 node의 for문 돌려 if not visited라면 특정 node depth에 +1(위 24446 문제 참고)

---

★ 21736 헌내기는 친구가 필요해 ★

 

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

def bfs(graph,x,y):
    queue=deque()
    queue.append((x,y))
    ans=0
    while queue:
        loc=queue.popleft()
        x,y=loc[0],loc[1]

        if 0<=(x-1):
            if graph[x-1][y] == 'O':
                graph[x-1][y] = 'X'
                queue.append((x-1,y))
            elif graph[x-1][y] == 'P':
                ans+=1
                graph[x-1][y] = 'X'
                queue.append((x-1,y))
        
        if (x+1)<=(N-1):
            if graph[x+1][y] == 'O':
                graph[x+1][y] = 'X'
                queue.append((x+1,y))
            elif graph[x+1][y] == 'P':
                ans+=1
                graph[x+1][y] = 'X'
                queue.append((x+1,y))

        if 0<=(y-1):
            if graph[x][y-1] == 'O':
                graph[x][y-1] = 'X'
                queue.append((x,y-1))
            elif graph[x][y-1] == 'P':
                ans+=1
                graph[x][y-1] = 'X'
                queue.append((x,y-1))

        if (y+1)<=(M-1):
            if graph[x][y+1] == 'O':
                graph[x][y+1] = 'X'
                queue.append((x,y+1))
            elif graph[x][y+1] == 'P':
                ans+=1
                graph[x][y+1] = 'X'
                queue.append((x,y+1))
    
    return ans

N,M=map(int,input().split())
campus=[]
x,y=0,0
for i in range(N):
    line=list(input().rstrip())
    if 'I' in line: x,y=i,line.index('I')
    campus.append(line)

ppl = bfs(campus,x,y)
if ppl == 0: print('TT')
else: print(ppl)

 

☝️ 전형적인 BFS 유형 문제. 시작점에서 양 방향 이동을 봐야 하므로 BFS로 각각의 경로를 확인한다. 

 

☝️ 주의점 - 무한 루프에 빠질 가능성이 있으므로, 한 번 방문한 곳을 X로 처리해 재방문 방지!

 

★ 한 곳에서 양 방향으로 탐색은 BFS 사용 ★

---

《최단경로》 ★ 1697 숨바꼭질 ★

 

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

def BFS(graph, visited, depths, start):
    visited[start] = True
    depths[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)
                return
            elif 0 <= child <= 100_000 and not visited[child]:
                visited[child] = True
                queue.append(child)
                depths[child] = depths[next_node] + 1
            else:
                pass

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

if N==K:
    print(0)
else:

    graph=[[] for _ in range(K+1)]
    visited=[False]*(100_000+1)
    depths=[-1]*(100_000+1)
    start = N

    BFS(graph, visited, depths, start)

 

☝️ 위 16953 문제와 동일. BFS의 depth로 N에서 K까지 가는 최단 경로 구하기

---

《최단경로》 ★ 7562 나이트의 이동 ★

 

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

def BFS(graph, start, end, depth):
    N=len(graph)
    visited=[[0]*N for _ in range(N)]

    queue=deque([start])
    visited[start[0]][start[1]] = True

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

    while queue:
        v=queue.popleft()

        for i in range(8):
            nx,ny=v[0]+dx[i],v[1]+dy[i]

            if 0<=nx<N and 0<=ny<N and not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx,ny))
                depth[nx][ny] = depth[v[0]][v[1]]+1
                if (nx,ny) == (end[0],end[1]):
                    return depth
                
for _ in range(int(input())):
    I=int(input())
    sx,sy=map(int,input().split())
    gx,gy=map(int,input().split())
    if (sx,sy) == (gx,gy):
        print(0)
    else:
        graph=[[0]*I for _ in range(I)]
        depth=[[0]*I for _ in range(I)]
        print(BFS(graph,(sx,sy),(gx,gy),depth)[gx][gy])

 

☝️ 출발점과 도착점이 주어진 상태에서 갈 수 있는 최단경로 구하기 - BFS의 depth 유형(위 2644 촌수계산과 동일)

 

☝️ 출발에서 도착점까지 가는 최단경로는 BFS의 depth. 따라서 graph외에 depth graph 만들어서 not visited라면 기존 상위 node depth + 1

---

《최단경로》 ★ 5014 스타트링크 ★

 

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

F,S,G,U,D=map(int,input().split())
button=0
if S==G:
    print(0)
else:
    queue=deque([S])
    visited=[0]*(F+1)
    depth=[0]*(F+1)
    dx=[U,-D]
    while queue:
        v=queue.popleft()
        visited[v] = True
        for i in range(2):
            nv=v+dx[i]
            if 1<=nv<=F and not visited[nv]:
                visited[nv]=True
                depth[nv]=depth[v]+1
                queue.append(nv)
    if depth[G]!=0:
        print(depth[G])
    else:
        print('use the stairs')

 

☝️ 일차원 배열에서 정해진 시작점과 끝 점 사이의 최단 거리 구하기이다. BFS idea + depths list 활용

---

《최단경로》 ★ 2178 미로 탐색 ★

 

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

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

def bfs(maze,start,end):
    queue = deque()
    queue.append((start,end))

    while queue:
        v = queue.popleft()
        x,y=v[0],v[1]

        if 0<=(x-1):
            if maze[x-1][y] == 1 and (x-1,y) != (0,0):
                maze[x-1][y] = maze[x][y] + 1
                queue.append((x-1,y))
        
        if (x+1)<=(N-1):
            if maze[x+1][y] == 1 and (x+1,y) != (0,0):
                maze[x+1][y] = maze[x][y] + 1
                queue.append((x+1,y))

        if 0<=(y-1):
            if maze[x][y-1] == 1 and (x,y-1) != (0,0):
                maze[x][y-1] = maze[x][y] + 1
                queue.append((x,y-1))

        if (y+1)<=(M-1):
            if maze[x][y+1] == 1 and (x,y+1) != (0,0):
                maze[x][y+1] = maze[x][y] + 1
                queue.append((x,y+1))

#graph
maze=[]
for _ in range(N):
    maze.append(list(map(int,input().rstrip())))

#bfs
bfs(maze,0,0)
print(maze[-1][-1])

 

☝️ 최단경로를 묻는 전형적인 그래프 문제 유형

 

☝️ 최단경로는 주어진 특정 노드에서 이동할 수 있는 모든 경우의 노드를 살펴보고, 노드마다 그 다음 노드로 이동할 수 있다면 1씩 계속 노드값을 더해 최종 마지막 [-1][-1]인 원소가 이동할 수 있는 최단경로의 수를 뜻한다.

 

☝️ 이 최단경로 유형은 따라서 BFS 유형으로, 주어진 노드에서 이동할 수 있는 모든 방향의 노드들을 살펴보아야 하므로, DFS 유형은 적합하지 않다. BFS로 매 노드 값을 계속 업데이트하면서 경로를 진행해야 함을 기억하자!

---

《최단경로》 ★ 16948 데스 나이트 ★

 

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

N=int(input())
chess=[[0]*N for _ in range(N)]
r1,c1,r2,c2=map(int,input().split())

def BFS(graph, visited, depths, start, dest):
    x,y=start[0],start[1]
    visited[x][y] = True
    depths[x][y] = 0
    queue = deque([start])
    while queue:
        v = queue.popleft()
        x,y=v[0],v[1]
        for i in range(6):
            nx,ny=x+dx[i],y+dy[i]
            if 0<=nx<N and 0<=ny<N:
                if visited[nx][ny] == False:
                    visited[nx][ny] = True
                    depths[nx][ny] = depths[x][y] + 1
                    if (nx,ny) == dest:
                        print(depths[nx][ny])
                        sys.exit()
                    queue.append((nx,ny))


start=(r1,c1)
dest=(r2,c2)

if start==dest:
    print(0)
    sys.exit()

visited=[[False]*N for _ in range(N)]
depths=[[-1]*N for _ in range(N)]
dx,dy=[-2,-2,0,0,2,2],[-1,1,-2,2,-1,1]

BFS(chess, visited, depths, start, dest)

print(-1)

 

☝️ 방향이 상하좌우 4방향이 아닌, 6방향이라는 점만 주의! 그리고 이동 뒤 목적지와 같다면 그 자리에서 depth 출력하고 프로그램 종료.

 

☝️ 결국에 queue 돌리면서 못찾았다면 함수 다 끝나고 난 뒤 -1 출력

 

+ BFS 함수 내에 그래프가 들어가지 않으므로 visited를 안만들고 graph 자체를 마킹하면서 1로 찍으면서 visited 기준 만들어도 된다.

---

★ 16173 점프왕 젤리 (Small) ★

 

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

N=int(input())
graph,visited=[],[[False]*N for _ in range(N)]
for _ in range(N):
    graph.append(list(map(int,input().split())))
dq=deque([(0,0)])
while dq:
    node = dq.popleft()
    x,y=node[0],node[1]
    visited[x][y]=True
    #right nx,ny
    rnx,rny=x,y+graph[x][y]
    if (rnx,rny) == (N-1,N-1):
        print('HaruHaru')
        sys.exit()
    if 0<=rny<N and not visited[rnx][rny]:
        dq.append((rnx,rny))
    
    #down nx,ny
    dnx,dny=x+graph[x][y],y
    if (dnx,dny) == (N-1,N-1):
        print('HaruHaru')
        sys.exit()
    if 0<=dnx<N and not visited[dnx][dny]:
        dq.append((dnx,dny))    
print('Hing')

 

☝️ 오른쪽과 아래로만 주어진 graph[x][y]만큼 이동하면 된다.

---