[코드트리 챌린지] 4주차 - DFS/BFS

dev_Hyun·2023년 9월 28일

코드트리 챌린지

목록 보기

4/8

0) 들어가기 앞서

지난 3주차에서는 NH 단계의 DP를 학습했다. 이전 주차들과 달리 해설을 봤던 문항들이 많았으며, 직접 코드를 구현해보지 않아 경험이 부족함을 많이 느꼈다.

1) 실력 진단 결과

슬프게도 진단 점수가 하락했다. 특히 DFS 유형으로 분류되는 실력진단 문제에서 return 문을 잘못된 부분에 작성해 다음 문제로 넘어가지 못했는데 뒤늦게 알아차린 것이 가장 아쉬웠다. (DP 유형 문제를 실력진단에서 꼭 만나보고 싶었는데 다음 주차엔 꼭 풀어보고 말겠다.)

동일하게 DFS/BFS 유형에 대해 부족하다는 결과를 받았다 😥

2) 4주차 학습 주요 내용

(이미지출처:https://howtolivelikehuman.tistory.com/75)

그래프 탐색의 방법으로 DFS(깊이우선탐색), BFS(너비우선탐색)이 있다.
그래프의 정점 간 연결관계를 표현하기 위해서 반드시 위 이미지와 같이 인접행렬 또는 인접리스트로 나타내어야 한다. 그러나 문제에서 2차원배열 격자형태로 주어지고 dxdy 기법을 활용해 제한된 이동만 가능할 경우 변환과정은 불필요 하다.
단, DFS는 재귀함수를 BFS는 Queue를 활용해야 풀이할 수 있다.
한번 탐색에 성공한 좌표를 중복해서 탐색하지 않도록 visited 배열을 활용하면 시간복잡도를 줄일 수 있다.

DFS

문제 1, 2

두 문제 모두 격자 내에서 영역을 구분하는 문제로 동일한 유형이다.
마을 구분하기 (링크 : https://www.codetree.ai/missions/2/problems/seperate-village?&utm_source=clipboard&utm_medium=text)
안전 지대 (링크 : https://www.codetree.ai/missions/2/problems/comfort-zone?&utm_source=clipboard&utm_medium=text)

리뷰 1

1) 첫 풀이와 개선점

격자 내에 남아있는 영역이 존재하는지 그리고 존재한다면 좌표를 알아내기 위해 while 반목문과 2개의 함수를 사용했었다.
2중 for 문을 사용하는 방법으로 개선할 수 있다. 모든 좌표에 접근하되 이동 가능한 좌표인지, 방문하지 않은 좌표인지 확인한다.

리뷰 2

1) 2차원 배열의 max/min 값 찾기

map() 함수를 이용하여 간편하게 찾을 수 있었다.

max(map(max, iterable object))

2) maximum recursion depth exceeded 에러

import sys
sys.setrecursionlimit(2500)

3) 첫 풀이와 개선점

동일한 환경(격자)을 사용하지 않기 때문에 처음 입력받은 격자를 조건이 변경될 때 마다 복사하여 사용했다. 이때 깊은 복사를 사용했다. (참고 링크 : https://black-hair.tistory.com/49)

BFS

풀이 pseudo code

from collections import deque

grid 입력으로 주어지는 격자
visitied 방문 여부를 저장할 격자
answer 방문 순서를 저장할 격자
order = 1 방문 순번
que = deque()
dxs = [방향전환]
dys = [방향전환]

def possible(x, y):
	if 격자 범위 밖:
    	return False
    if 이미 방문했거나, 장애물이 있는 경우:
    	return False
    return True

def push(x, y):
	answer[x][y] = order
    order += 1
    visited[x][y] = True
    que.append((x,y))
    
def bfs():
	while que:	# que에 요소가 존재한다면 반복
    	x, y = que.popleft()   # que에서 요소 pop
        for dx, dy in zip(dxs, dys):
        	nx, ny = x+dx, y+dy
            if possible(nx, ny):
            	push(nx, ny)

push(시작 좌표) # que에 시작지점 삽입
bfs()

answer, order 는 BFS 탐색의 탐색순서를 필요로 할 경우 사용된다.
방향전환/인접좌표로 이동 시 추가적인 규칙 또는 우선순위가 존재한다면 dxs/dys 배열을 다르게 정의할 수 있다.

문제1

K번 최댓값으로 이동하기 (링크 : https://www.codetree.ai/missions/2/problems/move-to-max-k-times?&utm_source=clipboard&utm_medium=text)

리뷰1

첫 번째 시도
- 테스트케이스도 통과하지 못해 북마크에 추가한 문항이다. 다음 좌표로 이동하기 위한 조건을 충족하기 위한 과정이 복잡했다.
- visited 배열에 True/False 대신 1 ~ k번 값을 저장했다.
두 번째 시도
- 각 과정을 외부함수로 분리하지 않고, k번 반복하는 for문 내부에서 주석으로 각 과정을 기술하여 구분했다. 과정이 복잡한 경우 오히려 순차적으로 작성한 코드가 가독성이 높았다.
- 동일한 visited 배열을 사용하는 대신 for문에서 k번에 해당하는 새로운 visited 배열을 새로 생성하였다.
- 함수의 반환값이 동일한 자료형일 필요가 없음을 알게되었다. 가령 아래와 같은 코드가 가능했다.
```
def find_next_position(max_val):
 global n, cnt

 for i in range(n):
     for j in range(n):
         if visited[i][j] and grid[i][j] == max_val:
             return i, j

 return False
```

문제2

돌 잘 치우기 (링크 : https://www.codetree.ai/missions/2/problems/clear-stones-well?&utm_source=clipboard&utm_medium=text)

리뷰

시도 중
1. 각 좌표의 우선순위를 파악하기 위해, 각 좌표에서 현재 위치를 포함해 몇 번의 이동이 가능한지 기록한다. 단, 현재 위치의 돌의 유무는 관계없이 카운팅 한다.
2. 돌을 제거할 수 있는 횟수가 남은 경우, 돌 좌표들 중 가장 높은 우선순위의 좌표 순으로 돌을 미리 제거해 둔다. 만약, 제거할 수 있는 횟수보다 동일 우선순위의 개수가 더 많은 경우 돌 좌표들을 새롭게 갱신한다.
3. 입력으로 제공되는 좌표를 기준으로 이동 가능한 횟수를 정답 후보로 선정한다.

3) 어느 상황에서 사용해야 할까?

DFS

격자 내에서 영역을 구분해야 하는 경우

BFS

탐색 시작 지점이 여러개인 경우 :
- 초기 queue에 시작 지점을 모두 삽입해도, 각 칸의 방문은 최대 1번이다. 따라서 시간복잡도는 O(n**2)
최단거리를 구해야 할 경우 :
- 현재 노드에서 가까운 곳부터 찾기 때문에 경로 탐색 시 첫번째로 찾아지는 해답이 곧 최단거리이다.

공통

모든 정점(지점)을 방문하는 것이 중요할 경우.

dev_Hyun

공룡, 다람쥐 그리고 돌고래!

이전 포스트

[코드트리 챌린지] 3주차 - DP

다음 포스트