섹션7: 깊이/넓이 우선 탐색(DFS, BFS ) 활용

BFS (Breadth First Search): 넓이 우선 탐색

 

1번: 최대 점수 구하기

for문 남발하지 말기

 

2번: 휴가

날짜를 인덱스로 하기 위해 T와 P에 insert(0, 0)함.

끝나는 조건문 유의하기: return!

 

3번: 양팔저울

 

4번: 동전 바꿔주기

edge - cut 잘하기

 

5번: 동전 분배하기

문제 읽은 뒤 DFS문제 같으면, 바로 코드 짜지 말고 상태 트리 그린뒤 코드 짜기.

1초 평가를 진행했을 때, best코드보다 내 코드가 더 효율적이라고 나왔다.

 

6번: 알파코드

 

7번: 송아지 찾기

for x in (a, b, c): 면 x가 a, b, c 순으로 된다.

 

8번: 사과나무

격자의 중심인 (n//2, n//2)에서부터 시작.

상하좌우를 탐색하니깐 4갈래로 시작. (시계방향으로: 12->3->6->9)

체크된 곳은 다시 방문하지 않는다.

마름모 모양으로 점점 커진다.

 

9번: 미로의 최단거리 통로

dist라는 행렬 만들기

최단거리 문제는 무조건 BFS

동심원으로 퍼지는 느낌

 

10번: 미로 탐색

한 곳으로 쭉 갔다가 돌아옴.

체크 박스를 따로 만들필요 없이 간 곳은 1로 바꾸기

 

11번: 등산 경로

갔던 곳인지 체크하기

 

12번: 단지 번호 붙이기 (DFS)

0행 0열부터 1열로 쭉 가면서 1이 있으면 거기서부터 탐색 시작.

다시 방문하지 못하게 해당 부분 0으로 바꾸기.

더 갈 곳 없으면 0행 2열부터 또 1 찾을 때까지 계속 탐색.

 

13번: 섬나라 아일랜드 (BFS)

BFS로 풀기.

위와 같은 방식이지만, Q가 아무것도 없을 때 cnt += 1하기

 

14번: 안전영역

반복하여 계산해야해서 체크 박스를 따로 둔다.

파이썬으로 재귀함수할 때 time limit을 해주면 좋다: sys.setrecursionlimit(10**6)

 

15번: 토마토

익은 토마토의 좌표를 먼저 Q에 넣는다. (1, 2) (3, 5)

dis는 익은 날들. 초기화: 0

큐를 팝한 후 안 익은 토마토를 익은 토마토로 바꾸면서 dis의 해당값 날짜 추가하기. 그 뒤 큐에 넣기.

 

16번: 사다리 타기

2를 기준으로 출발.

왼쪽과 오른쪽 먼저 보기.

 

17번: 피자배달거리

처음에 for문 돌리면서 집과 피자집 정보를 찾는다.

집은 hs 리스트에 저장

피자집은 pz 리스트에 저장

피자집 6개 중 4개가 살아남는다. → 6C4 (이걸 DFS로 한다.)