DFS로 블록을 만드는 예술적인 방법? -테트로미노-
1. 문제
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
이차원 배열에 주어진 블록중 하나를 놓아봐서 거기에 적힌 수의 합의 최댓값을 구하는 문제
2. 풀이
항상 이걸 어떻게 해?라고 두려워하지말고
어렵게 생각하지 말고
성실하게 완전탐색을 구현하면 풀린다는 생각으로
심플하게 5가지 블록의 회전,대칭 모든 가능한 경우를 만들어서 모든 좌표에 대해 조사해보면 진짜로 최댓값이 나오긴 해
근데 변수를 어디서 초기화해야하는지, 그런 실수가 쉽게 나오더라
블록의 회전,대칭은 19가지가 가능해서 당연히 실수하기 쉬우니
성실하게, 꼼꼼하게
from sys import stdin
def search_maps(n,m,maps,i):
global max_value
#0번째 블록
#회전으로 2가지 가능
if i == 0:
for y in range(n):
for x in range(m):
sum_value1 = 0
sum_value2 = 0
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+2,y
dx4,dy4 = x+3,y
if dx2 <= m-1 and dx3 <= m-1 and dx4 <= m-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x,y+3
if dy2 <= n-1 and dy3 <= n-1 and dy4 <= n-1:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
#1번째 블록
#회전해도 1가지만 가능
elif i == 1:
for y in range(n):
for x in range(n):
sum_value = 0
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x,y+1
dx4,dy4 = x+1,y+1
if dx2 <= m-1 and dy3 <= n-1 and dx4 <= m-1 and dy4 <= n-1:
sum_value += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value:
max_value = sum_value
#2번째 블록
#회전,대칭으로 8가지가 가능함
elif i == 2:
for y in range(n):
for x in range(m):
sum_value1 = 0
sum_value2 = 0
sum_value3 = 0
sum_value4 = 0
sum_value5 = 0
sum_value6 = 0
sum_value7 = 0
sum_value8 = 0
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x+1,y+2
if dy2 <= n-1 and dy3 <= n-1 and dx4 <= m-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y
dx4,dy4 = x+2,y
if dy2 <= n-1 and dx3 <= m-1 and dx4 <= m-1:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+1,y+1
dx4,dy4 = x+1,y+2
if dx2 <= m-1 and dy3 <= n-1 and dy4 <= n-1:
sum_value3 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x-1,y+1
dx4,dy4 = x-2,y+1
if dy2 <= n-1 and dx3 >= 0 and dx4 >= 0:
sum_value4 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x-1,y+2
if dy2 <= n-1 and dy3 <= n-1 and dx4 >= 0:
sum_value5 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+2,y
dx4,dy4 = x+2,y+1
if dx2 <= m-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value6 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x,y+1
dx4,dy4 = x,y+2
if dx2 <= m-1 and dy3 <= n-1 and dy4 <= n-1:
sum_value7 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y+1
dx4,dy4 = x+2,y+1
if dy2 <= n-1 and dx3 <= m-1 and dx4 <= m-1:
sum_value8 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
if max_value < sum_value3:
max_value = sum_value3
if max_value < sum_value4:
max_value = sum_value4
if max_value < sum_value5:
max_value = sum_value5
if max_value < sum_value6:
max_value = sum_value6
if max_value < sum_value7:
max_value = sum_value7
if max_value < sum_value8:
max_value = sum_value8
#3번째 블록
#회전,대칭으로 4가지가 가능
elif i == 3:
for y in range(n):
for x in range(m):
sum_value1 = 0
sum_value2 = 0
sum_value3 = 0
sum_value4 = 0
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y+1
dx4,dy4 = x+1,y+2
if dy2 <= n-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x,y+1
dx4,dy4 = x-1,y+1
if dx2 <= m-1 and dy3 <= n-1 and dx4 >= 0:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+1,y+1
dx4,dy4 = x+2,y+1
if dx2 <= m-1 and dy3 <= n-1 and dx4 <= m-1:
sum_value3 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x-1,y+1
dx4,dy4 = x-1,y+2
if dy2 <= n-1 and dx3 >= 0 and dy4 <= n-1:
sum_value4 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
if max_value < sum_value3:
max_value = sum_value3
if max_value < sum_value4:
max_value = sum_value4
#4번째 블록
#회전,대칭으로 4가지 가능
else:
for y in range(n):
for x in range(m):
sum_value1 = 0
sum_value2 = 0
sum_value3 = 0
sum_value4 = 0
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+2,y
dx4,dy4 = x+1,y+1
if dx2 <= m-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x-1,y+1
if dy2 <= n-1 and dy3 <= n-1 and dx4 >= 0:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x-1,y+1
dx4,dy4 = x+1,y+1
if dy2 <= n-1 and dx3 >= 0 and dx4 <= m-1:
sum_value3 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y+1
dx4,dy4 = x,y+2
if dy2 <= n-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value4 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
if max_value < sum_value3:
max_value = sum_value3
if max_value < sum_value4:
max_value = sum_value4
n,m = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(n)]
max_value = 0
#모든 블록의 모든 가능한 경우에 대해, 모든 좌표에서 조사해봄
for i in range(5):
search_maps(n,m,maps,i)
print(max_value)
3. 다른 풀이
어떤 고수들은 블록의 모양이 길이가 4인 DFS의 탐색 모양이라는 점에 주목했다
보라색 블록을 제외한 모든 블록은 한 점에서 길이가 4인 DFS로 탐색하면 모두 찾아볼 수 있다는 점이다
그래서 보라색 블록만 내가 만들었던 함수 이용해서 예외처리하고
나머지 블록은 DFS 하나로 처리해보면
from sys import stdin
#보라색 블록을 제외한 나머지 블록을 그려서 합을 구해보는 함수
def dfs(x,y,n,m,maps,visited,s,sum_value):
global max_value
#길이가 4가 된다면, 탐색을 중지하고 최댓값 갱신
if s == 4:
if max_value < sum_value:
max_value = sum_value
else:
for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
dx = x + ni
dy = y + nj
if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
visited[dy][dx] = 1
dfs(dx,dy,n,m,maps,visited,s+1,sum_value+maps[dy][dx])
visited[dy][dx] = 0
#보라색 블록을 만들어서 합을 구하는 함수
def search_blocks(x,y,maps,n,m):
global max_value
sum_value1 = 0
sum_value2 = 0
sum_value3 = 0
sum_value4 = 0
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+2,y
dx4,dy4 = x+1,y+1
if dx2 <= m-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x-1,y+1
if dy2 <= n-1 and dy3 <= n-1 and dx4 >= 0:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x-1,y+1
dx4,dy4 = x+1,y+1
if dy2 <= n-1 and dx3 >= 0 and dx4 <= m-1:
sum_value3 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y+1
dx4,dy4 = x,y+2
if dy2 <= n-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value4 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
if max_value < sum_value3:
max_value = sum_value3
if max_value < sum_value4:
max_value = sum_value4
n,m = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(n)]
visited = [[0]*m for _ in range(n)]
max_value = 0
for y in range(n):
for x in range(m):
#시작 지점을 방문 처리하고,
visited[y][x] = 1
#시작 지점의 합을 읽어서 DFS를 들어가야지
#길이는 1이고
dfs(x,y,n,m,maps,visited,1,maps[y][x])
#탐색이 끝나면, 시작 지점 복구하고 visited를 원래 초기 상태로
#이러면 visited를 다시 만들 필요가 없다
visited[y][x] = 0
#보라색 블록 탐색
search_blocks(x,y,maps,n,m)
print(max_value)
근데 이렇게 하면 시간 초과가 나더라??
이제 더 고수들은 backtracking을 이용해서.. 시간을 단축시키는데
배열 내에 존재하는 최댓값을 먼저 찾는다
DFS로 탐색을 하다가 현재까지 구한 sum_value에 가능한 최댓값을 더해서 계산한 값이, 현재까지 전체 최댓값보다 작다면
해볼 필요가 없으므로 재귀 경로를 끊어준다는 것
전체 배열의 최댓값이 max_maps라면..
만약 길이가 2까지 탐색했다면, 그때의 sum_value에 나머지 길이 2 * max_maps를 합한 sum_value + max_maps*2가
전체 최댓값 max_value보다 작다면, 해볼 필요가 없다는 것
길이 s까지 탐색했다면.., sum_value + max_maps*(4-s)가 max_value보다 작다면.. 해볼 필요가 없다는 것
이렇게까지 하면 3배 더 빠른 시간으로 통과할 수 있다
from sys import stdin
#보라색 블록을 제외한 나머지 블록을 그려서 합을 구해보는 함수
def dfs(x,y,n,m,maps,visited,s,sum_value,max_maps):
global max_value
#만약 현재 전체 최댓값이, block이 읽을 수 있는 가능한 최댓값
#sum_value + max_maps*(4-s)보다 크다면
#더 이상 탐색할 필요가 없다
if max_value > sum_value + max_maps*(4-s):
return
#길이가 4가 된다면, 탐색을 중지하고 최댓값 갱신
if s == 4:
if max_value < sum_value:
max_value = sum_value
else:
for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
dx = x + ni
dy = y + nj
if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
visited[dy][dx] = 1
dfs(dx,dy,n,m,maps,visited,s+1,sum_value+maps[dy][dx],max_maps)
visited[dy][dx] = 0
#보라색 블록을 만들어서 합을 구하는 함수
def search_blocks(x,y,maps,n,m):
global max_value
sum_value1 = 0
sum_value2 = 0
sum_value3 = 0
sum_value4 = 0
dx1,dy1 = x,y
dx2,dy2 = x+1,y
dx3,dy3 = x+2,y
dx4,dy4 = x+1,y+1
if dx2 <= m-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value1 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x,y+2
dx4,dy4 = x-1,y+1
if dy2 <= n-1 and dy3 <= n-1 and dx4 >= 0:
sum_value2 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x-1,y+1
dx4,dy4 = x+1,y+1
if dy2 <= n-1 and dx3 >= 0 and dx4 <= m-1:
sum_value3 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
dx1,dy1 = x,y
dx2,dy2 = x,y+1
dx3,dy3 = x+1,y+1
dx4,dy4 = x,y+2
if dy2 <= n-1 and dx3 <= m-1 and dy4 <= n-1:
sum_value4 += (maps[dy1][dx1]+maps[dy2][dx2]+maps[dy3][dx3]+maps[dy4][dx4])
if max_value < sum_value1:
max_value = sum_value1
if max_value < sum_value2:
max_value = sum_value2
if max_value < sum_value3:
max_value = sum_value3
if max_value < sum_value4:
max_value = sum_value4
n,m = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(n)]
#2차원 배열에서 가장 큰 값을 찾는다
#maps는 각 원소가 리스트인 2차원 리스트인데
#map(max,maps)를 한다면, 각 원소별로 최댓값을 찾아서 하나의 리스트가 나올거고
#거기서 또 max를 하면 전체 max가 나오겠지
max_maps = max(map(max,maps))
visited = [[0]*m for _ in range(n)]
max_value = 0
for y in range(n):
for x in range(m):
#시작 지점을 방문 처리하고,
visited[y][x] = 1
#시작 지점의 합을 읽어서 DFS를 들어가야지
#길이는 1이고
dfs(x,y,n,m,maps,visited,1,maps[y][x])
#탐색이 끝나면, 시작 지점 복구하고 visited를 원래 초기 상태로
#이러면 visited를 다시 만들 필요가 없다
visited[y][x] = 0
#보라색 블록 탐색
search_blocks(x,y,maps,n,m)
print(max_value)
이제 조금 더 고수는 보라색 블록도 DFS로 그릴 수 있다는 것에 주목했다
한 지점에서 DFS로 탐색을 하다가, 길이가 2인 상태가 된다면...
현재 지점에서 다시 DFS 탐색을 수행하는데 딱 1번만 더 탐색을 하면 된다는 것이다
그러니까 나머지 블록은 길이가 4인 DFS로 그리는데
보라색 블록은 길이가 3인 DFS로 그릴 수 있다는 것이다
from sys import stdin
#보라색 블록을 제외한 나머지 블록을 그려서 합을 구해보는 함수
def dfs(x,y,n,m,maps,visited,s,sum_value,max_maps):
global max_value
#만약 현재 전체 최댓값이, block이 읽을 수 있는 가능한 최댓값
#sum_value + max_maps*(4-s)보다 크다면
#더 이상 탐색할 필요가 없다
if max_value > sum_value + max_maps*(4-s):
return
#길이가 4가 된다면, 탐색을 중지하고 최댓값 갱신
if s == 4:
if max_value < sum_value:
max_value = sum_value
else:
for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
dx = x + ni
dy = y + nj
if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
#탐색을 하다가 길이가 2가 된다면
#보라색 블록을 그리기 위해
if s == 2:
visited[dy][dx] = 1
#현재 지점 (x,y)에서 다시 dfs를 수행한다
#이때 길이 1을 더해주고, 다음 값을 읽은 상태로 들어가면
#읽은 지점으로 가지 않고 다른 지점으로 이동할 수 있잖아
dfs(x,y,n,m,maps,visited,s+1,sum_value+maps[dy][dx],max_maps)
visited[dy][dx] = 0
#여기는 보라색 블록 말고 다른 블록을 그리도록 if문이랑 상관없이 계속 수행
visited[dy][dx] = 1
dfs(dx,dy,n,m,maps,visited,s+1,sum_value+maps[dy][dx],max_maps)
visited[dy][dx] = 0
n,m = map(int,stdin.readline().split())
maps = [list(map(int,stdin.readline().split())) for _ in range(n)]
#2차원 배열에서 가장 큰 값을 찾는다
#maps는 각 원소가 리스트인 2차원 리스트인데
#map(max,maps)를 한다면, 각 원소별로 최댓값을 찾아서 하나의 리스트가 나올거고
#거기서 또 max를 하면 전체 max가 나오겠지
max_maps = max(map(max,maps))
visited = [[0]*m for _ in range(n)]
max_value = 0
for y in range(n):
for x in range(m):
#시작 지점을 방문 처리하고,
visited[y][x] = 1
#시작 지점의 합을 읽어서 DFS를 들어가야지
#길이는 1이고
dfs(x,y,n,m,maps,visited,1,maps[y][x])
#탐색이 끝나면, 시작 지점 복구하고 visited를 원래 초기 상태로
#이러면 visited를 다시 만들 필요가 없다
visited[y][x] = 0
print(max_value)
보라색 블록을 그리는 방법이 재밌는데 다시한번 잘 이해해본다면..
for ni,nj in [[0,1],[1,0],[0,-1],[-1,0]]:
dx = x + ni
dy = y + nj
if dx >= 0 and dx <= m-1 and dy >= 0 and dy <= n-1 and visited[dy][dx] == 0:
#탐색을 하다가 길이가 2가 된다면
#보라색 블록을 그리기 위해
if s == 2:
visited[dy][dx] = 1
dfs(x,y,n,m,maps,visited,s+1,sum_value+maps[dy][dx],max_maps)
visited[dy][dx] = 0
먼저 s=1일때, 현재 (x,y)지점의 maps[y][x]를 읽었어
다음 지점으로 이동을 하겠지
s=2로 오면.. 이제 여기도 읽었는데
s=2에서 s=3으로 갈때.. 어떻게 가는지를 잘 생각해보자
s=3에서 (dx,dy)로 이동을 한 상태라면 dfs(dx,dy,...,3,...)로 가겠지
그런다면 s=4에서는 어떻게 이동을 할까?
(dx,dy)로 들어가버리면 s=4에서는 이런 블록이 만들어지겠지
하지만 원하는 보라색 블록은 이렇게 만들어지는게 아니다
(dx,dy)의 값은 읽어오지만, (dx,dy)로 들어가지 않는게 핵심이다
(dx,dy)의 값은 읽어오고, 읽어오면 그 블록은 그려지는거지만 그곳으로 가지 않으면 된다
다시 (x,y)에서 dfs 탐색을 하면 s=4일때 양 옆으로만 이동이 가능해서 보라색 블록을 그릴 수 있게 된다.
아니 양 옆으로만 이동이 가능하다고?
왜냐하면 (dx,dy)는 가지도 않았고, 읽어오기만 했는데 visited[dy][dx]=1로 방문처리까지 했기때문에
(x,y)에서 다시 s=4일때 이동을할려고하면, (dx,dy)지점은 가지 않는다
따라서 이렇게 하면, 간단한 함수를 구현할 수 있고, 앞선 풀이보다 3배 더 빠르게 할 수 있다
맨 첫 풀이보다 10배 더 빠르다
4. 되돌아보기
블록을 그리는 방법? 평소에 어렵게 생각했지만
index로 그냥 블록을 만들어버리든지
아니면 dfs로 자취를 그리면 블록 형태가 된다는거 기억을 해놓으면.. 비슷한 문제에서 써먹을 수 있지 않을까
보라색 블록을 만드는 놀라운 트릭은 기억할 필요가 있을것 같다
'알고리즘 > DFS BFS 정복기' 카테고리의 다른 글
| BFS 최단경로 역추적하는 방법 배우기 (0) | 2023.02.07 |
|---|---|
| 3차원 BFS에서 조금은 섬세한 디테일 -공주님을 구해라!- (0) | 2022.11.13 |
| 이동가능한지 많은 것을 고려해야하는 BFS -탈주범 검거- (0) | 2022.09.26 |
| DFS/BFS 정복하기 -영역을 구분하는 BFS의 성질 응용- (0) | 2022.09.23 |
| BFS/DFS 정복기 -memoization을 이용한 효율적인 탐색- (0) | 2022.09.18 |
TAGS.
