16_bfs_최단거리
# ref: https://www.acmicpc.net/problem/18352
거리k인 문제!!
1) 앞에서 봤던 지도들과 차별점 : 연결에 방향성이 있음!!!!
2) 도시 사이의 연결이 단순 연결이 아니라 : 거리 정보--> 모두 1로 동일!!
참고) 최단 거리 : 최단 거리 알고리즘 여러가지 존재!!!
==> BFS를 기반으로 일반화하는 다익스타알고리즘!!! etc
# 문제를 분석!!!
===> 왜 이 문제가 탐색의 문제!!!! + 외 최단거리 문제...
:DFS/BFS/다른 방식,,,,,++++경우의 수........etc
===> 최단 거리 관련된 : 지나온 경로에 대한 BFS 사용!!!
출발점을 중심으로 체계적으로 접근/탐색!!!!!
---> 여러 스타일/유형을 접해야 함!!방법도 1개 아님!!!
# 백준 사이트 : 입력에 대한 부분을 직접 처리!!!--> 귀찮음;;;
# 입력부분1) n,m,k.x 대한 기본정보
===> map 함수를 잘 사용하면 편해요1!!!
input("도시수,도로수,기준거리,출발도시").split(" ")
도시수,도로수,기준거리,출발도시4 4 2 1
['4', '4', '2', '1']
n,m,k,x = input("도시수,도로수,기준거리,출발도시").split(" ")
n
도시수,도로수,기준거리,출발도시4 4 2 1
'4'
n = int(n)
m = int(m)
k = int(k)
x = int(x)
n
4
n,m,k,x = map(int, input("도시수,도로수,기준거리,출발도시").split(" "))
n
도시수,도로수,기준거리,출발도시4 4 2 1
4
# 입력 2번째 : 도로 연결에 대한 정보를 받아야 함!!!
==> 도시별로 연결성을 인접리스트 방식으로 표현!!!!
:코드화 입장 (파이썬 리스트/dict)==> 리스트!!!!
==> 문제상 도시 : 1, 2,3,4,,,,,n
파이썬 정수index : (0),1,2,3,4,.,,,,n
graph = [ [] for _ in range(n+1)]
graph
[[], [], [], [], []]
# 입력3 : 실제 연결들을 받아서 graph에 추가 처리!!!!
--> 지도에 코드화!
: 출발도시 도착도시
for _ in range(m):
# 4 2 : 출발도s, 도착도시e ==> 그래프에 정리!!!
s,e = map(int, input("출발도시 도착도시 공백으로하세요..").split(" "))
graph[s].append(e)
graph
출발도시 도착도시 공백으로하세요..1 2
출발도시 도착도시 공백으로하세요..1 3
출발도시 도착도시 공백으로하세요..2 3
출발도시 도착도시 공백으로하세요..2 4
[[], [2, 3], [3, 4], [], []]
# cf) 문제 상황에 따라서 연결별로 거리가 제각각이면,,
(도착도시, 거리/가중치/요금...)
==> 문제 상황에 따라서 가변적임!!
# 출발점을 중심으로 순차적으로 단계별로 진행 : BFS 방식!!!!
# BFS 기본 아이디어
- 할 일에 대한 것 : 그 도시에서 연결된 정보 ---> 기존과 동일....
- 한 일에 대한 것 : 방문 순서에 있어서는 큰 의미X + 거리......
거리에 대한 정보로 기록을 하면 좋을 것!!!(튜닝!!)
distance = [inf(0), inf(1), inf(2), inf(3),inf(4)]
출발점 x=1 // q=[1]
distance = [inf(0), 0, inf(2), inf(3),inf(4)]
//////////////////////// 탐색 : 출발점 중심. ///////
갈 곳 : 1 ---> 2번
갔던 곳인지 / 새로운 곳이지
new판단 : 그 곳의 거리 inf 인지 체크1!!
할 일 : 거리를 갱신(기존+1)
distance = [inf(0), 0, 0+1, inf(3),inf(4)]
또 여기서 갈 수 있는 도시 할 일에 추가
append/extendf( 3/4)
.................. 할 일이 없을 때 까지.......
d = [ inf(0), 0, 1, 1, 2]
d.index(k) : 1개만 찾아지게 되니까 문제가 발새을 함!!!
==> LC/ enumerate........ : 필터링!!!!! --> 출력!!!!
distance = [inf(0), inf(1), inf(2), inf(3),inf(4)]
q = [1]
distance = [inf(0), 0 , inf(2), inf(3),inf(4)]
////////////////////////
--->pop(0) : now =1, q =[]
: graph[1] : [2,3]
1) next_node = 2
# new/old : 2번 거리 inf
distance = [inf(0), 0 , 0+1, inf(3),inf(4)]
# 추가 방문할 곳
q=[2] ******
2) next_node = 3
# new/old : 3번거리 inf
distance = [inf(0), 0 , 0+1, 0+1,inf(4)]
# 추가 방문할 곳
q = [2]+[3]=[2,3]
---> pop(0) : now = 2, q=[3]
: graph[2] : [3,4]
1) next_node = 3
distance = [inf(0), 0 , 0+1, 0+1,inf(4)]
# new/old : pass
2) next_node = 4
# new/old : inf(4) : 신규!!!!
distance = [inf(0), 0 , 0+1, 0+1,1+1]
# 추가 방문할 곳 : 4추가
q= [3]+[4] = [3,4]
---> pop(0) : now = 3, q= [4]
: graph[3] : []
--> pop(0) : now = 4: q=[]
: graph[4] : []
----------------------------------------------->
distance = [inf(0), 0 , 0+1, 0+1,1+1]
from collections import deque
def bfs_city(start):
# 할 일 : 방문할 도시 -=-> 기존 bfs와 동일함 : deque
q = deque()
# 한 일 : 방문한 도시 --> 수정!!! 거리로 수정!!!!!
# : 초기값에 대한 세팅 못가요!!! 거리가 겁나 멀어요 ing
# + 도시가 1번 부터 있어서 0번의 가상도시....
INF = float("inf")
distance = [INF] * (n+1) # 0번 가상 도시 포함
# [inf(0), inf(1),inf(2),inf(3),inf(4)]
# 초기화
# 2-1) 할 일에 대한 초기화
q.append(start)
# 2-2) *** 출발점에 대한 거리정보 초기화 *****다른 점!!!!
distance[start] = 0
# 큰 틀 : 방문할 도시가 없을 때 까지~~~~~~
while q:
# 어디로 갈까요???--> 할 일을 꺼내야 : bfs --> 앞에서
now = q.popleft()
# *** 지금 여기서 1칸으로 연결되 도시들을 다 체크!!!!!!
for next_node in graph[now]:
# now에서 1칸으로 연결된 도시가,,,신규 방문지 체크!!!!
if distance[next_node] == INF:
# 거리를 갱신!!! 도장!!!!
distance[next_node] = distance[now] + 1
# 새롭게 할 일 부여 받으면 됨 : next_node에 가서 1칸씩 갈 수 있으면 가봐!!!
q.append(next_node)
return distance
bfs_result = bfs_city(x)
bfs_result
[inf, 0, 1, 1, 2]
==> 필터링 : 값이 k인 친구들만 선택!!!!
필터링 : 값으로 필터링
출력은 : 정수인덱스 = 도시번호
---> enumerate
+++ 도시 출력에 대해서 정수인덱스를 사용했으니 오름차순 큰 요소!!!
dis_k = [ i for i,v in enumerate(bfs_result ) if v == k]
dis_k
[4]
# 출력에 대한 조건
1) 조건을 만족하는 경우가 없다면 : -1출력!!
2) 조건을 만족한다면 : 만족하는 것들 다 1개에 1줄씩!!(밑으로)]
if dis_k == []:
print(-1)
else:
# 탐색에 대한 while을 연습/리뷰를 위해서.. : while
while dis_k:
print(dis_k.pop(0))
4
# 정리)
- 기본적인 탐색 DFS/ BFS 중에서 어떤 것을 활용할 수 있을까!!!
- 거리에 대한 문제 세팅 : 한 일에 대한 세팅 수정!!!!
--> 못가요 : INF
출발점 : 0 etc
- 출발점 중심으로 순차적인 부분이 중요할 떄 : BFS 중심
순차적인 부분이 중요하지 않을 떄 : DFS고려!!!
기능적으로 반복이 반복 : 재귀함수---> DFS ***
- 거리가 동일한 경우 : BFS로(탐색으로도 거리문제 해결 가능함!!)
거리가 가중치가 있는 일반적인 경우 : 최단거리 알고리즘 적용!!!
++++ 모든 가능한 경우의 수 문제 : 탐색!!!!!
17_탐색_미로탈출문제
# 문제 : https://www.acmicpc.net/problem/2178
# 미로 탐색 문제
기본적인 DFS/BFS --> k거리도시문제 ---> 미로 탐색문제!!
( k거리 도시문제 + 지도상 움직 구현 )
# 분석 : 2차원에서 평면상의 움직임 + 모든 방문을(탐색)+ 순차+거리!!!!
====> k거리 도시 문제 + 지도상LRUD이동
----- 2차원 평면상 움직일 수 있음!!! : in/out--> 부등식
----- 탐색 : 기존에 한 일에 대한 세팅 : k도시 스타일....
+++ 주어진 2차원 처리!!!
+++ 기존 지도에 갱신!!!
: DFS(X): 왔다리갔다리--> 순서를 최소로 추적하기 부적당!!!
: BFS :순차적으로 출발점 기준에서 한 걸음씩 진행!!!
==> BFS 탐색 방식으로 해야 함!!!!
deque를 사용해서 큐방식으로 코드를 구현하자!
# 입력 처리1) 지도 크기(가로, 세로)
n,m = map(int, input("가로 세로 크기를 입력하세요").split(" "))
print(n,m)
가로 세로 크기를 입력하세요4 6
4 6
"1 0 1 1 1".split(" ")
['1', '0', '1', '1', '1']
[i for i in "10111"]
['1', '0', '1', '1', '1']
# 입력처리2) 지도의 실제 값을 받는 부분
===> 큰 틀 : 가로줄
graph = []
for i in range(n):
t = input("n,m에 대한 {0}번째 가로줄".format(i+1))
t = list(map(int, [i for i in t])) # [1,0,1,1,1]
graph.append(t)
graph
n,m에 대한 2번째 가로줄101010
n,m에 대한 3번째 가로줄101011
n,m에 대한 4번째 가로줄111011
[[1, 0, 1, 1, 1, 1],
[1, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1]]
graph[가로][세로] #--> 2차원 좌표
graph[0][0]
1
graph[0][0]
0
# 잠시 이 문제를 해결해 보세요!! 직접!!!!
# ===> 구현에서 LRUD 이동 문제 + k거리 도시 문제 섞인 문제!!!!!!
# 대략적인 아이디어!!!
-- 할 일 : q --> deque(큐) : [ (x_pos,y_pos),,,,,,,]
-- 한 일 : 거리 --> graph에 직접 기록!!!!
--> start: (0,0)
q:[ (0,0)]
-------------- 실제 돌아야 함!!!
방문할 곳을 선택 : bfs--> pop(0) [in/out & 벽/길 & 처음/후발]
(0,0) --> L : (-1,0) out :pass
--> R : (1,0) & 값0 벽 : pass
--> U : (0,-1) out : pass
--> D : (0,1) in & 값1 ==> new
--> 도장 : 지금까지 값 + 1
--> 거기 가서 또 1칸씩 이동할 수 있는 해봐!!
q:[ (0,1)]
---------------------------------------
(0,1) --> L
--> R
--> U : ok--> q[(0,0)]
--> D : ok --> q[(0,0), ( 0,2)]
----------------------------------------
(0,0) --> L
--> R
--> U
--> D
q[(0,2)]
----------------------------------------
(0,2) --> L......
# 실제 탐색을 위한 부분을 수정 : LRUD
==> 앞에 했던 방식 중 그냥 하나를 사용하겠습니다.
dx = [-1,1,0, 0]
dy = [0, 0,1, -1]
# ===> 특별하게 순서는 의미가 없어서,,,그냥 1칸 이동을 퉁!!!
from collections import deque
# 차이점 : 문제출제(1,1)로출발 ---> 파이썬 리스트로 코드화!!!
파이썬(0,0)
++++++ 1장소/node : 2차원 ======> (x_pos, y_pos)
def bfs_miro(start): # ( 0,0)
# 기본 세팅
# 1-1) 할 일 : deque --> [ (x_pos,y_pos),,,,,]
# 1-2) 한 일 : 거리(1씩 누적) : graph에 직접 갱신!!!
q = deque()
# ---> 처음 위치에 대한 처리!!!
x_pos = start[0]
y_pos = start[1]
# ---> 할 일에 추가..
q.append( (x_pos, y_pos) )
# ==> 입력값으로 준 시작칸에 대한 좌표
# 큰 틀 : 할 일이 없을 때 까지....
while q:
# 해야하는 일을 선택/방문지 선택 : bfs --> 큐->맨앞
# deque : popleft()
# (0,0)
now_x, now_y = q.popleft()
# 지금 칸에서 인접한 칸을 이동한다면,,,,LRUD
for i in range(4): # 4가지 인접 이동 LRUD
next_x = now_x + dx[i]
next_y = now_y + dy[i]
# --> now에서 LRUD1칸 이동해본다면,,next
# 체크1) in./out
if 0<=next_x<n and 0<=next_y<m: # 파이썬의 인덱스중심 & in
# --> 지도안에 LRUD 이동 가능한 경우들...
# 체크2) 내가 온 곳이 처음인지(이동가능한지도 포함)
if graph[next_x][next_y] == 1:
# 값을 갱신!!!! 지금 값 + 1 도장찍기
graph[next_x][next_y] = graph[now_x][now_y] + 1
# 이동할수 있으니,,거기가서 또 1칸씩 이동할 수 있는지 해봐!!!
q.append( (next_x, next_y))
bfs_miro( (0,0) )
graph
[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 15]]
graph[n-1][m-1]
15
18_탐색_얼음얼리기
[DFS/BFS] 음료수 얼려 먹기 (실전문제, 이것이 코딩테스트다 with 파이썬)
DFS (깊이 우선 탐색 알고리즘) : 깊이 우선 탐색, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 BFS (너비 우선 탐색 알고리즘) : 너비 우선 탐색, 가까운 노드부터 탐색하는 알고리즘 문
kk-yy.tistory.com
앞의 미로 탐색 문제를 살짝 수정해서..
==> 모든 점에서 탐색을 하도록 하는 점이 차이점!!!!!!
---> 일단 말씀드린 대로 할 수 있는 것 같다ㅣ..이해....
출발점을 모든 점으로 해서 각기 0--->1 카드 뒤짚기!!!:탐색!
---> DFS/ BFS 왜 또이또이!!!!
---> DFS가 가능하면,,,,재귀함수로,,,,
# 시도1) DFS/BFS : 큰 틀만 체크
큰 틀 : 모든 좌표에서 탐색(0-->1로 뒤짚기&이어진 부분에서만)
for i in 가로줄:
for j in 세로줄 :
==> 2D상의 임의 좌표(i,j) 출발점!!!
if (i,j)시작할 수 있다면,,
탐색을 시작하고, 끝날떄까지..
카운팅 +1 갱신!!!!
# 설명을 편히 하기위해서 인덱스는 사람중심(1,1) : 코드(0,0)
# 출발점 : (1,1)~~~~~~(n,m)
(1,1) --> 시작 가능한 출발점 체크 : (i,j)값이 0인 경우만 시작
==> 시작이 가능하다고 판단!!!
이것을 출발점으로 시작!!!
도장찍기(1,1)에 값을 1로 도장찍고 ...
==> (1,1)에서 LRUD 4가지 방향을 다 가봐!!! : 할 일 받으면,,
L = [(1,1)L, (1,1)R, (1,1)U, (1,1)D]
==> 다음 할 일 BFS--> 맨 앞
(1,1)L =(0,1) : outbound --> pass
L = [ (1,1)R, (1,1)U, (1,1)D]
==> 다음 할 일
(1,1)R = (1,2) : IN & 얼음얼릴수 있는지 체크 0
(1,2)에 값을 1로 도장찍고
(1,2)에서 할 일을 부여받기!!
L = [ (1,1)U, (1,1)D, (1,2)L,(1,2)R,(1,2)U,(1,2)D]
==> 다음 할 일
(1,1)U = (0,1) : outbound --> pass
L = [ (1,1)D, (1,2)L,(1,2)R,(1,2)U,(1,2)D]
==> 다음 할 일
(1,1)D = (2,1) : IN&얼음얼릴 수 있는 체크 0
(2,1)에 값을 1로 도장찍고
(2,1)에 할 일 부여받기!!!
L = [ (1,2)L,(1,2)R,(1,2)U,(1,2)D,(2,1)L,(2,1)R,(2,1)U,(2,1)D]
==> 다음 할 일
(1,2)L=(1,1) : IN & 이미 1 : pass
L = [(1,2)R,(1,2)U,(1,2)D,(2,1)L,(2,1)R,(2,1)U,(2,1)D]
==> 다음 할 일
(1,2)R=(1,3) : in & 이미1 : pass
L = [(1,2)U,(1,2)D,(2,1)L,(2,1)R,(2,1)U,(2,1)D]
==> 다음 할 일
(1,2)U = (0,2) : out : pass
L = [(1,2)D,(2,1)L,(2,1)R,(2,1)U,(2,1)D]
==> 다음 할 일
(1,2)D = (2,2) : in & 값0
(2,2)에 값을 1로 도장찍기
(2,2)에서 할 일을 부여받기
L = [(2,1)L,(2,1)R,(2,1)U,(2,1)D,(2,2)L,(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,1)L = out
L = [(2,1)R,(2,1)U,(2,1)D,(2,2)L,(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,1)R => in & 이미 값이 1 : pass
L = [(2,1)U,(2,1)D,(2,2)L,(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,1)U ==> in & 이미 값이 1 : pass
L = [(2,1)D,(2,2)L,(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,1)D ==> in & 이미 값이 1 : pass
L = [(2,2)L,(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,2)L =(2,1) => in & 이미 값이 1 : pass
L = [(2,2)R,(2,2)U,(2,2)D]
==> 다음 할 일
(2,2)R = (2,3) : in & 값0--> 할일
(2,3) 값을 1로 변경!!
(2,3)할 일 부여 받음
L = [(2,2)U,(2,2)D,(2,3)L,(2,3)R,(2,3)U,(2,3)D]
==> 다음 할 일
(2,2)U : pass
L = [(2,2)D,(2,3)L,(2,3)R,(2,3)U,(2,3)D]
==> (2,2)D : pass
L = [(2,3)L,(2,3)R,(2,3)U,(2,3)D]
==> (2,3)L : pass
L = [(2,3)R,(2,3)U,(2,3)D]
==> (2,3)R : pass
L = [(2,3)U,(2,3)D]
==> (2,3)U : pass
L = [(2,3)D]
==> (2,3)D : pass
L = []
탐색이 종료가 되었습니다!!!!!!!!!(1,1)시작한 탐색이 종료!!
+1 카운팅!!!!!
(1,2) : start X
(1,3) : start X
(1,4) : start X
(1,5) : 시작할 수 있음!!!!
=> (1,5)도장1로 찍고
(1,5)할 일을 받으면 됨!!!
L = [(1,5)L, (1,5)R, (1,5)U, (1,5)D]
-->
(1,5)L : pass
(1,5)R : pass
(1,5)U : pass
(1,5)D : pass
L = []
탐색이 종료가 되었습니다.(1,5)에서 시작하는 탐색이 종료!!
카운팅 +1
(2,1)
(2,2)
....
(4,5)
# 이 문제 조건을 코드화
graph_45 = [
[0,0,1,1,0],
[0,0,0,1,1],
[1,1,1,1,1],
[0,0,0,0,0]
]
graph_45
[[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]
# BFS로 탐색하는 경우로 해서 한 번 작성해보세요!!!!
==> 몇 개의 얼음 덩어리냐!!!!
graph = graph_45.copy()
graph
[[0, 0, 1, 1, 0], [0, 0, 0, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]]
n = 4
m = 5
from collections import deque
# BFS로 탐색하는 경우로 해서 한 번 작성해보세요!!!!
==> 몇 개의 얼음 덩어리냐!!!!
입력 : 출발점에 대한 정보(row, col) 좌표!!!
기능 : 출발점에서 이동이 가능하면,,모두 다 이동하고 체크!!!
BFS/DFS
출력 : 출발점에서 시작할 수 있고, 그래서 다 방문을 하면 1
출발점에서 시작을 할 수 없다면,, 0
def bfs_ice( row_init, col_init):
# 1) 주어진 시작점에서 시작할 수 있는지 체크
if graph[row_init][col_init] ==0:
# 2) 방문할 곳들에 대한 : 할 일에 대한 초기 세팅!!!
q = deque([ [row_init, col_init] ]) # 괄호 주의!!
graph[row_init][col_init] = 1 # 도장찍기...
# 할 일 : graph에서 LRUD를 돌아가면서 할 일 없을 때 까지..
while True: # --> 무한 루프...
if not q:
return 1
# 갈 곳에 대한 선택!!! bfs
row, col = q.popleft()
# 직접 LRUD에 대해서 이동을 체크!!!
for dx, dy in [ [0,-1], [0,1], [-1,0], [1,0] ]:
# --> 이동 가능한지 체크 in/out
if 0<=row+dx<n and 0<=col+dy<m: # 지도안쪽
# ==> 얼음을 얼릴 수 있는 공간인지 체크!!!!
if graph[row+dx][col+dy]==0:
graph[row+dx][col+dy] = 1
q.append( [row+dx, col+dy ])
else:
return 0
# 위의 함수를 세팅에 적용!!!
graph = graph_45.copy()
n = 4
m = 5
cnt = 0 # --> 카운팅용!!!!
for row in range(n):
for col in range(m):
# 시작점 row, col
cnt += bfs_ice(row, col) # if graph[row][col] == 0:
print(cnt)
3
## 이 문제는 카드 뒤집기를 하는데,,,순서X
==> 0-->1로 바꾸기만 하면 됨!!!!!!
DFS // BFS 탐색의 순서는 의미가 없고,,,그냥 다 하면 끝!!!!
==> 위의 코드에서 popleft()--> pop()
==>이 문제는 DFS로 탐색을 해도 된다!!!!!!!!
*** DFS 풀 수 있다!!! ==> 재귀함수로 구현할 수 있음!!!!
===> 기능 중심의 코드를 작성할 수 있어서!!!!!! 점화식처럼!!!
def dfs_recursive( row, col):
# 기능 중심!!!
# 기능1) 주어진 점이 in.out 체크!!!
if row <=-1 or row >=n or col <=-1 or col >=m: # out
return False
# 기능2) 인바운드이면 ===> 얼음을 얼릴 수 있는지 체크!!!
if graph[row][col]==0:
# 2-1) 도장찍기
graph[row][col] = 1
# 2-2) LRUD 더 갈 수 있는지 체크!!!!
dfs_recursive(row, col-1) # L : L막히기 전까지 ~~~쭉 L
dfs_recursive(row, col+1) # R
dfs_recursive(row-1,col) # U
dfs_recursive(row+1, col) # D
# 혹시 문제에서 L을 먼저 하세요......
# 탐색의 순서가 정해져있다고 하면,,,순서에 맞춰서 세팅!!!
return True
return False
# 정리!
DFS/ BFS 모두 가능한 문제!
==> 본인 편한대로 하시면 됨!
DFS 사용이 가능하다! ==> Stack ==> 정의 or 재귀함수!
--> 재귀함수 : 기능 중심으로 할 일에 규칙을 코드화!
--> 정의대로 : 준비물(할일,한일) : 열심히 돌면 됨!!
BFS 사용이 가능하다 ==> 큐 ==> deque
==> 거리, 출발점, 순서가 중요할 때!
: 출발점에서 뭔가 점진적으로 진행을 할 때 고려 방법!
==> 최단 거리 문제 기본이 되는 방법 중 한 : 다익스트라알고리즘
(거리가 1인 경우/ 일정한 경우 : BFS로 가능!)
==> 속도 이슈!! popleft()!!
주의!) 재귀함수로 하면 안됨! 결과가 이상함!
+++ 순수하게 경우의 수 문제처럼 모든 경우를 다 탐색하는 스타일도 있음!
https://school.programmers.co.kr/learn/courses/30/lessons/92343
프로그래머스
SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
//다음 시간에..
**주말에 꼭!!
==> 지금까지 한 파이썬 문법들을 숙지!!
==> 기본문제 유형 : 달달
+++ 알고리즘 : 이해 + 기본 유형
*** 퇴실 버튼
===> sql : 최단거리 알고리즘 + 탐색
다음주 파이썬 퀴즈
'ASAC 빅데이터 분석가 7기 > ASAC 일일 기록' 카테고리의 다른 글
| ASAC 빅데이터 분석가 과정 9일차 - 2 (24.12.16) (0) | 2024.12.16 |
|---|---|
| ASAC 빅데이터 분석가 과정 9일차 - 1 (24.12.16) (1) | 2024.12.16 |
| ASAC 빅데이터 분석가 과정 8일차 - 1 (24.12.13) (2) | 2024.12.13 |
| ASAC 빅데이터 분석가 과정 7일차 - 2 (24.12.12) (0) | 2024.12.12 |
| ASAC 빅데이터 분석가 과정 7일차 - 1 (24.12.12) (0) | 2024.12.12 |